M3/4P14 Elementary Number Theory Problem Sheet 3.

This ‘double-sized’ sheet is assessed coursework. Please hand in solutions to the starred questions (i.e., to questions 1, 3, 4, 13 and 14) at the end of the lecture on Tuesday the 9th of December. As for non-assessed problems if you don’t have much time I suggest trying questions 5, 6, 7, 8 and 10 first.

1^{∗}) Let p be an odd prime, and let n be an integer not divisible by p. Prove that n is a square modulo p^{2} if and only if n is a square modulo p.

2) Here is a low-level proof of the Fermat-Euler theorem. Let m and a be integers such that m > 0 and hcf(a, m) = 1.

(a) The map x ↦ \overline{a}x is a bijection from (Z/m)^{∗} to itself (write down an inverse). Deduce that ∏_{s∈(Z/m)^{∗}} s = ∏_{s∈(Z/m)^{∗}} \overline{a}s in (Z/m)^{∗}.

(b) Define P = ∏_{s∈(Z/m)^{∗}} s. Deduce from (a) that P = \overline{a}^{ϕ(m)}P. Conclude that a^{ϕ(m)} ≡ 1 mod m.

3^{∗}) Find all integers n > 1 such that −1 is a primitive root modulo n.

4^{∗}) What is the highest order of integers modulo 72? Find an integer of that order.

5) (a) Find all the elements of (Z/11Z)^{×} that have order n mod 11, for (i) n = 2 (ii) n = 3 (iii) n = 5

(b) What are the primitive roots mod 11?

6) What are all the primitive roots mod 9? Mod 10? Mod 12?

7) If n > 1 and n is not a prime, then prove that (n−1)! is not congruent to −1 mod n. Hence Wilson’s theorem gives a primality test, that is, if n > 1 is an integer, then we can test to see whether n is prime by working (n − 1)! and seeing if it is −1 mod n.

8) a) Let n = 651693055693681. It can be checked on a computer that 2^{n−1} ≡ 1 mod n. Can we deduce, just from this information, that n is prime?

b) Let m = 651693055693709. It can be checked on a computer that 2^{m−1} ≡ 613609515736831 mod m. Can we deduce, just from this information, that m is not prime?

c) Find (m − 1)! mod m for all composite numbers m.

9) Let a ∈ Z have order k mod m. Let h ≥ 1 be an integer. Prove that a^{h} has order k mod m if and only if hcf(h, k) = 1.

10) Let m ≥ 3 be an integer, and let a be any integer. Prove that a^{2} is not a primitive root mod m.

11) Prove that 3 is a primitive root mod 5^{2003}. (This question is harder than others. Hint: use the ideas from the proof of Theorem 5.8.)

12) (a) Find infinitely many solutions to n = 3ϕ(n).

(b) Prove that n = 4ϕ(n) has no solutions.

(c) Is there an integer t > 4 such that n = tϕ(n) has a solution?

13^{∗}) (a) Find r_{p}(−3) when p is a prime number of the form 1 + 6m.

(b) The same question for primes of the form 5 + 6m.

(c) Deduce the formula for the Legendre symbol (\frac{−3}{p}), where p is a prime different from 2 and 3.

(d) Prove that there are infinitely many primes of the form 1 + 6m.

14^{∗}) Let p > 3 be a prime. Deduce from the previous question a formula for (\frac{3}{p}) (without using quadratic reciprocity). Hence verify the quadratic reciprocity law for p and 3.

15) Let p be an odd prime. Let k be an integer not divisible by p. Prove that

∑_{n=0}^{p−1} (\frac{n(n + k)}{p}) = −1.