NUMBER THEORY AND CRYPTOGRAPHY 2023: ASSIGNMENT 4
DUE: 6PM FRIDAY 13TH OCTOBER
For full marks, you must show your working and provide supporting arguments and proofs
where appropriate. You may use a pocket calculator for numerical computations.
(1) (22 marks)
(a) (7 marks) Find an integer a with 0 ≤ a < 11 that is simultaneously a primitive
root modulo 11, 22, 121, and 14641. You should give an argument showing that
the integer you have found has this property.
(b) (7 marks) Make a table of the discrete logarithms modulo 11 (with respect to
whichever base r you like).
(c) (8 marks) For m = 121, determine the possible values of ordm(a) and determine
how many congruence classes mod m have each order.
(2) (22 marks) Find all solutions to the following congruences using discrete logarithms:
(a) (7 marks) 7x7 ≡ 3 mod 11
(b) (7 marks) 14x21 ≡ 85 mod 99 (Hint: use the CRT.)
(c) (8 marks) 18x ≡ 111 mod 121 (Hint: you might warm up by solving it modulo
11 first.)
(3) (42 marks, 7 marks each)
(a) Prove that φ(n) ≤ n− 1 and the equality holds if and only if n is prime.
(b) Prove that if n is a composite integer, then
φ(n) ≤ n−√n.
(c) Let us denote d(n) the number of positive divisors of n. For example, d(6) = 4
because 1, 2, 3, and 6 are the positive divisors of 6. Prove that
d(n) ≤ 2√n.
(d) Prove that
φ(n) + d(n) ≤ n+ 1.
(e) Prove that d(n) is a multiplicative function. Namely, for all coprime m and n,
d(mn) = d(m)d(n).
(f) Show that φ(n) + d(n) = n+ 1 if and only if n is prime or equal to 1 or 4.
(4) (14 marks)
(a) (7 marks) Prove that φ(n)|n!.
(b) (7 marks) Prove that if n is an odd integer, then n | 2n! − 1. (Hint: recall how
we proved there are infinitely many Fermat’s pseudoprimes.)