University of Toronto
Faculty of Arts and Sciences
MAT315H1 - S: Introduction to Number Theory
Fall 2023
Homework 5
1 Problems to be submitted
Make sure you follow all the indications as stated in the syllabus.
1. (a) (2 points) Let p be an odd prime. Prove that
(p− 1)! ≡ −1 (mod p)
Recall that the factorial means (p− 1)! = 1× 2× · · · × (p− 2)× (p− 1).
Hint: Pair each residue with its multiplicative inverse.
Remark: The above result is known as Wilson’s Theorem.
(b) (3 points) Let p be an odd prime with p ≡ 1 (mod 4). Prove that
x2 ≡ −1 (mod p)
is solvable.
Hint: Write p = 4k + 1 and use Wilson’s Theorem.
2. (5 points) Consider the polynomial X2 + 7X + 3. Describe, with justification, which are the primes for
which the polynomial is irreducible, those for which it has two different roots, and those for which it has
a repeated root modulo p.
Hint : Recall the quadratic formula that you studied in a previous homework.
Remark: These kind of questions are very important in number theory and, for higher degree polyno-
mials, very challenging to answer. Eventually congruences are not enough to describe the primes that
fullfill the different roles.
In his paper, Representation theory, its rise and role in Number Theory, Langlands mentions of the same
problem but for the polynomial x5 + 10x3 − 10x2 + 35x− 18 the following:
It is irreducible modulo p for p = 7, 13, 19, 29, 43, 47, 59, · · · and factors into linear factors modulo p for
p = 2063, 2213, 2953, 3631, · · · . These lists can be continued indefinitely, but it is doubtful that even the
most perspicacious and experienced mathematician would detect any regularity. It is none the less
there.
3. Determine whether the following congruences are solvable. You must justify your process clearly and all
computations must be explained.
(a) (2 points) X2 ≡ 107 (mod 293).
(b) (2 points) X2 ≡ 2043 (mod 2671).
(c) (2 points) X2 ≡ 9117 (mod 10037).
1
(d) (2 points) X2 + 7X ≡ 1 (mod 101).
(e) (2 points) X2 −X ≡ 3 (mod 1009).
Remark: All the modulus used in this previous congruences are prime numbers.
4. This problem is the consummation of all the themes and topics we have covered up to Quadratic Reci-
procity. It constitutes one of the major results of Number Theory of the times of Fermat, Euler, Gauss,
etc. The following result was conjectured by Fermat:
Let p ≡ 1 (mod 4) be a prime number. Then it is the sum of two squares, that is, there are integers x
and y with p = x2 + y2.
It is fair to say that this result and its proof constitutes historically the start of algebraic number theory.
Fermat didn’t provide a proof. The first known proof is due to Euler. The one we explore below is from
Dedekind.
In this problem p is a prime number with p ≡ 1 (mod 4).
(a) (1 point) Use problem 1 of this homework to conclude that there exists integers X and K with
X2 + 1 = pK.
(b) (2 points) Factoring the left hand side in the Gaussian integers we have
(X + i)(X − i) = pK.
Prove that p does not divide, in the Gaussian Integers, either of X + i or X − i.
(c) (2 points) Justify carefully why part (b) implies p is not a prime in the Gaussian Integers.
(d) (1 point) Justify carefully why part (c) implies there exist two Gaussian integers a+ bi and c+ di,
that are not units, with
p = (a+ bi)(c+ di).
(e) (1 point) Prove that
p2 = (a2 + b2)(c2 + d2).
(f) (2 points) Prove that
p = a2 + b2.
(g) (1 point) Explain how this result, together with other facts we have seen in the course, complete
the proof of the following fact: An odd prime number is a sum of two squares if and only if
p ≡ 1 (mod 4).
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 9.4: 1, 2, 3, 4, 5
From Illustrated Theory of Numbers: Chapter 8, Exercises 1,2, 5, 7, 9, 10
Page 2
3 Suggested readings and comments
From Number theory of George E. Andrews: Chapter 9, section 9 provides a proof of the Quadratic
Reciprocity Law.
It is an interesting proof, that shows the strength of techniques of what is sometimes known as Geometry
of Numbers. The main point of this proof is Gauss Lemma
Unfortunately, it is a proof that does not really explains why the quadratic reciprocity law is true
besides the fact that it proves it. Good proofs in this sense, require more advanced algebraic number
theory.
From Illustrated Theory of Numbers: To read Chapter 8 is a good idea, but it might take time. For
purposes of the course it is not necessary.
That said, it includes an interesting proof of Quadratic Reciprocity that is different from the one in
the other book. This one uses permutations and their sign, via Zolotarev’s Lemma.
It is once more a very interesting proof, but still it doesn’t really explains why quadratic reciprocity is
true. For this, there is not really a way to avoid more advanced algebraic number theory.
Page 3