University of Toronto
Faculty of Arts and Sciences
MAT315H1 - S: Introduction to Number Theory
Fall 2023
Homework 3
1 Problems to be submitted
Make sure you follow all the indications as stated in the syllabus.
1. Solve the following systems of congruences or explain why they do not have solutions. In case there are
solutions they must be given in the modulus that is the LCM of the congruence modulus.
(a) (1 point) 13X ≡ 3 (mod 15), 2X ≡ 6 (mod 10).
(b) (2 points) X2 ≡ 1 (mod 10), X2 ≡ 3 (mod 187)
(c) (2 points) X + 2Y ≡ 3 (mod 7), 3X + 5Y ≡ 1 (mod 21).
2. (a) (2 points) Let (m,n) = 1. Let X (mod mn) be a congruence class that under the Chinese Remain-
der Theorem corresponds to A (mod m) and B (mod n)
Prove that X (mod mn) is a cube if and only if A (mod m) and B (mod n) are cubes.
(b) (2 points) Let p ̸= 3 be a prime number. How many cubic residues are there modulo p?
Hint: Use primitive roots. The answer depends on the congruence of p modulo 3.
(c) (1 point) Without computing explicitly, find the number of congruence classes modulo 9797 that
are cubes.
3. In this problem we prove a formula for Eulers Totient Function ϕ that depends on prime factorization.
(a) (3 points) Let m,n be positive integers with g.c.d(m,n) = 1. Prove that
ϕ(mn) = ϕ(m)ϕ(n).
Hint: Use the Chinese Remainder Theorem.
(b) (2 points) Let p be a prime numbers and α a positive integer. Prove that
ϕ(pα) = pα − pα−1.
(c) (2 points) Suppose the prime factorization of n is given by
n = pα11 ...p
αk
k .
Prove that
ϕ(n) = n
(
1− 1
p1
)
· · ·
(
1− 1
pk
)
.
(d) (1 point) Use the previous parts to compute ϕ(212).
1
(e) (2 points) Define the analogous Euler Totient function Φ for the Gaussian Integers. That is, for a
Gaussian Integer z, Φ(z) is the number of congruence classes modulo z that are invertible modulo
z.
Compute Φ(18 + 81i). Explain your process.
4. (10 points) Euler’s Totient Functions is a very peculiar function. Gauss proved the following result:
For a positive integer n, we have ∑
d|n
ϕ(d) = n.
The sum runs over the positive divisors of n.
In this problem we will prove this result. For each integer 1 ≤ k ≤ n− 1 define
Ak := {a (mod n)|k is the the smallest integer with ka ≡ 0 (mod n)}
(a) (2 points) Prove that if k1, k2 are different, then Ak1 , Ak2 are disjoint.
(b) (3 points) Prove that if Ak is nonempty, then k|n.
Hint: If k does not divide n and ka ≡ 0 (mod n), you can find a smaller k′ with k′a ≡ 0 (mod n).
(c) (2 points) Let k|n. Prove that
|Ak| = ϕ(k).
(d) (2 points) Use the previous facts to prove Gauss theorem.
(e) (1 point) Illustrate Gauss’ Theorem by explicitly showing the sets Ak for n = 18.
2 Suggested exercises and problems from the book and other
sources.
Do not submit any of these!
From Number theory of George E. Andrews: Section 5-2: 1, 2; Section 5-3: 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 16, 18, 19, 20; Section 5-4: 1, 2, 4, 5, 6
3 Suggested readings and comments
From Number theory of George E. Andrews: Section 4-2; Section 4-3 talks about powers and shuf-
fling. I wont return to this later in the course, but is a nice read; Chapter 5 in its entirety should be
readable by the end of this week.
On problem 3 of this homework: Functions with the property exhibited in 3(a) are very common in
number theory. They are called multiplicative functions. Some other examples that will appear
later in the course are the total number of divisors, the sum of divisors or the number of distinct prime
factors and, most importantly, Dirichlet Characters!
On problem 4 of this homework: Sums that run over divisors of an integer are very common in number
theory. They have a lot of structure, and it is frequent to give proofs of their values by similar methods
as this one (i.e. by counting and interpreting cardinalities of some sets).