University of Toronto
Faculty of Arts and Sciences
MAT315H1 - S: Introduction to Number Theory
Fall 2023
Homework 4
1 Problems to be submitted
Make sure you follow all the indications as stated in the syllabus.
1. (5 points) We know that 3 is a primitive root modulo 31. You can use this without proof.
Using that fact, or otherwise, find all elements of all possible orders modulo 31. Your answers for each
order must be given in the residues −15,−14, ..., 14, 15.
You must explain your reasoning carefully.
Hint: There is a (very) painful way to do this and an easy way to do this. We have seen in the proof of
the existence of primitive roots how the easy way works.
2. (5 points) Let p be an odd prime. Prove that 2p admits a primitive root.
Hint: We have seen in lecture that p has a primitive root. Use the chinese remainder theorem to reduce
to that case.
3. Compute the value of the following Legendre Symbols. All the values in the denominators are primes.
Note: You are not allowed to use the quadratic reciprocity law, in case you are familiar with it. You
must compute these values using the definition and basic properties of the Legendre Symbol.
(a) (2 points)
(
3
7
)
,
(b) (2 points)
(
101
11
)
,
(c) (2 points)
(
5
17
)
,
(d) (2 points)
(
13
29
)
,
(e) (2 points)
(−1
101
)
.
4. Let p be an odd prime number. Prove the following facts about squares modulo p.
(a) (2 points) The number of quadratic residues modulo p is the same as the number of nonquadratic
residues.
(b) (2 points) The product to two quadratic residues is again a quadratic residue.
(c) (2 points) The product of two nonquadratic residue is a quadratic residue.
(d) (2 points) The product of a quadratic residue and nonquadratic residue is a nonquadratic residue.
1
(e) (2 points) Use the previous facts to justify that the Legendre Symbol satisfies(
ab
p
)
=
(
a
p
)(
b
p
)
,
for any integers a, b.
Hint: Use primitive roots to prove facts (a) to (d). For (e), to avoid too much repetitive explanation,
try to use a table to compare values of both sides of the equation.
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 7.1: 1, 2, 3, 4, 5, 6, 7 (problem 7 is important);
Section 7.2: 4, 15, 16. Section 9.1: 1; Section 9.2.
3 Suggested readings and comments
From Number theory of George E. Andrews: Chapter 7 should be readable in a comfortable way by
the end of the week. Sections 9.1 and 9.2 also should be readable in a comfortable way.
Page 2