MAT202H5F - Introduction to Discrete Mathematics
Fall 2020
Assignment 2: Due November 13, 2020 (Friday) at 9:00PM.
Answers must be submitted via Crowdmark using your personalized submission link (which will be sent to
your email). Make sure your answer to each question starts in a different file.
Late submissions will not be accepted.
Instructions
A template for this assignment is available on Quercus; you may upload this template to Overleaf and
compile your work there. Check the guide in the notes and the Quercus assignments page for more details
on uploading to Crowdmark.
Q1. Prove Exercise 4.6.12 in the course notes. Then, assuming that gcd(a, n)|b, determine how many solutions
(in Zn) the congruence
ax ≡ b (mod n)
has. Explain your reasoning and provide examples to support your claim.
(Hint: Look at Example 4.3.2.)
Q2. Let φ(n) be Euler’s phi function.
(a) Show that
1 + 21 + 22 + 23 + · · ·+ 2φ(15)−1 ≡ 0 (mod 15)
but
1 + 31 + 32 + 33 + · · ·+ 3φ(15)−1 6≡ 0 (mod 15).
(b) Prove that if gcd(a, n) = 1 and gcd(a− 1, n) = 1, then
1 + a+ a2 + a3 + · · ·+ aφ(n)−1 ≡ 0 (mod n).
End of Assignment 2
1
How you will be graded
Q1.
3 points for proving 4.6.12; 3 points for number of solutions and examples; 2 points for writing.
Q2.
(a) 2 points; (b) 3 points; 2 points for writing.
2

欢迎咨询51作业君