M3/4P14 Elementary Number Theory Answers Sheet 3.

1^{∗}) (4 marks) It is clearly enough to prove that if n ≡ m^{2} mod p for some m ∈ ℤ, then n ≡ ℓ^{2} mod p^{2} for some ℓ ∈ ℤ. We look for ℓ of the form ℓ = m + kp, where k ∈ ℤ. We have n = m^{2} + rp for some r ∈ ℤ. By assumption hcf(n, p) = 1 hence hcf(m, p) = 1. To find k we need to solve the congruence

m^{2} + rp ≡ n ≡ ℓ^{2} ≡ m^{2} + 2mkp + k^{2}p^{2} ≡ m^{2} + 2mkp mod p^{2}.

This reduces to rp ≡ 2mkp mod p^{2}, which is equivalent to r ≡ 2mk mod p. Since hcf(2m, p) = 1 (p is odd) there exists an integer s such that 2ms ≡ 1 mod p. Now k = rs is a solution. Finally, the square of ℓ = m + rsp is congruent to n modulo p.

3^{∗}) (2 marks) n = 2 is the only integer greater than 1 such that −1 ≡ 1 mod n The order of −1 mod 2 is 1. On the other hand, ϕ(2) = 1, so −1 is a primitive root mod 2. Let n > 2. Then the order of −1 is 2. However ϕ(n) = 2 implies that the only prime factors of n are 2 or 3 (otherwise ϕ(n) ≥ ϕ(p) = p − 1 ≥ 4), 9 does not divide n (otherwise ϕ(n) ≥ ϕ(9) = 6), and 8 does not divide n (otherwise ϕ(n) ≥ ϕ(8) = 4). The possible values of n are 4, 3, 6, 12. But ϕ(12) = 4, whereas ϕ(n) = 2 in all the other cases. The final answer is: n is 2, 3, 4 or 6.

4^{∗}) (4 marks) CRT says that for an integer t we have t^{a} ≡ 1 mod 72 if and only if t^{a} ≡ 1 mod 9 and t^{a} ≡ 1 mod 8. Since ϕ(9) = 6 we have t^{6} ≡ 1 mod 9. On the other hand, the square of any odd number is 1 mod 8 (check!). Thus we also have t^{6} ≡ 1 mod 8, and this implies t^{6} ≡ 1 mod 72. If t is an odd primitive root mod 9, then t is coprime to 72, and has order 6 mod 72.

2 is a prime root mod 9, but 2 is not odd, so we add 9 to it and get 11. Another possible answer is 5.

(Note that the order of any element divides ϕ(72) = ϕ(8)ϕ(9) = 24, but this bound is not very good!)

In group-theoretic terms the argument runs as follows. The group (ℤ/72)^{∗} is isomorphic to the product of groups (ℤ/8)^{∗} and (ℤ/9)^{∗}. The group (ℤ/9)^{∗} is cyclic of order 6, so that the 6-th power of any element in this group is 1. On the other hand, the square of any element in (ℤ/8)^{∗} is 1. Hence the 6-th power of any element in the product (ℤ/8)^{∗} × (ℤ/9)^{∗} is 1. Any element of (ℤ/8)^{∗} × (ℤ/9)^{∗} with second coordinate of order 6, has order 6.

5) The order of an element mod 11 will divide ϕ(11) = 10, so must be either 1, 2, 5 or 10. One could now just multiply everything out, but one can use a little thought and make the total amount of work done much smaller:

The only element of order 1 is clearly 1. If an element x has order 2 then x^{2} ≡ 1 mod 11 so x ≡ ±1 mod 11 (by Lemma 3.14), and so 10 is the unique element of order 2. Next we will find all the elements of order 5 by brute force—note that if an element doesn’t have order 1, 2 or 5, then it must have order 10.

We start with 1, which has order 1. Next 2—we see that 2^{5} = 32 ≡ −1, so 2 doesn’t have order 1, 2 or 5, so it has order 10. Similarly 3^{5} = 243 ≡ 1 mod 11 (I hope you remember the test for divisibility by 11!), so 3 has order 5 mod 11. Next 4^{5} = 1024 ≡ 1 mod 11, so 4 has order 5 mod 11.

I don’t know 5^{5} so we’ll have to do 5 the long way. 5^{2} = 25 ≡ 3, so 5^{3} ≡ 3 × 5 = 15 ≡ 4 and 5^{4} ≡ 4 × 5 ≡ 20 ≡ 9. Finally 5^{5} ≡ 9 × 5 = 45 ≡ 1, and so 5 has order 5.

For the rest, note the trick that (−a)^{5} = −a^{5}, so we don’t have to do any more work. We see that 6^{5} ≡ −5^{5} ≡ 10, so 6 has order 10. Similarly 7^{5} ≡ −4^{5} ≡ 10 so 7 must also have order 10. In the same way, 8 has order 10, but 9 has order 5 because 9^{5} ≡ −2^{5} ≡ 1. Finally 10 has order 2, we did that one already. Note that the elements of order 5 have come out to be 3,4,5 and 9, and there are 4 = ϕ(5) of them, and this agrees with Corollary 5.4.

So the answer to the question is: (a) (i) 10, (ii) none, (iii) 3,4,5,9 and (b) 2,6,7,8.

6) Brute force gives that 2 and 5 work mod 9, 3 and 7 work mod 10, and nothing at all works mod 12 (cf. Theorem 5.12).

7) If n > 1 and n is not a prime, then choose some prime p|n. Then p|(n − 1)! and hence p can’t divide (n − 1)! + 1. In particular, n can’t divide (n − 1)! + 1 either.

8) a) We know that if p > 2 is prime then 2^{p−1} is 1 mod p. But this doesn’t say anything about what happens if p is not prime. So we can’t deduce anything at all about n. In fact, n is not prime! It’s 72931.87517.102103.

b) If m were prime then 2^{m} ≡ 1 mod m. So m cannot be prime either.

c) The answer is: (m − 1)! ≡ 0 mod m unless m = 4. Write m = p_{1}^{a_{1}} … p_{r}^{a_{r}}, where the p_{i} are pairwise distinct primes. If r ≥ 2, then p_{i}^{a_{i}} ≤ m−1 for all i = 1, …, r, hence n, the product of these prime powers, divides (m − 1)!. Thus in this case (m − 1)! ≡ 0 mod m. If r = 1, then n = p^{a}, a ≥ 2. Consider separately the case when p is odd and p = 2. If p is odd, then p^{a−1} ≤ p^{a}, 2p^{a−1} ≤ p^{a}, hence p^{a}|2p^{2a−2}|(p^{a} − 1)!, so that in this case we also have (m − 1)! ≡ 0 mod m. If m = 2^{a}, a ≥ 3, then 2 and 2^{a−1} are two different factors of (2^{a}−1)!, hence the same conclusion. The only exceptional case is m = 4, where (m − 1)! ≡ 2 mod 4.

9) This can be seen pretty easily using group theory. I’ll translate it down into number-theoretic terms though. Let b = a^{h}.

If hcf(h, k) > 1 then choose some prime p dividing h and k. Then b^{k/p} ≡ a^{k(h/p)} ≡ 1^{h/p} ≡ 1 and in particular, b cannot have order as big as k.

Conversely, if hcf(h, k) = 1, then choose λ > 0 such that λh ≡ 1 mod k. Then b^{λ} ≡ a mod m, and so if b has order d then b^{d} ≡ 1 and so a^{hd} ≡ 1. Hence hd must be a multiple of k, by definition of “order”. However, h is prime to k, and so by Corollary 1.7 of the course, k must divide d. We deduce that the order of b is at least k. But b^{k} is easily checked to be 1 mod m, and so the order of b is exactly k.

10) By definition, a primitive root mod m is an element of (ℤ/m)^{∗} of order ϕ(m), and so we can instantly deal with an easy case of the question: if hcf(a, m) > 1 then hcf(a^{2}, m) > 1 and so a^{2} isn’t a primitive root mod m.

Let’s assume a ∈ (ℤ/m)^{∗}. Suppose for a contradiction that a^{2} has order ϕ(m) mod m. Note that ϕ(m) is even. Note also that if g is a primitive root mod m then 1, g, g^{2}, …, g^{ϕ(m)−1} mod m give us all the elements of (ℤ/m)^{∗}, so in particular if a^{2} is a primitive root then a ≡ (a^{2})^{t} mod m for some t. Now a ∈ (ℤ/m)^{∗} and hence a^{2t−1} ≡ 1 mod m. But this means that ϕ(m) divides 2t − 1, but ϕ(m) is even and 2t − 1 isn’t, a contradiction.

11) In the proof of Theorem 5.8 we’ve seen that if g is a primitive root mod p = 5, say g = 3, then either g or g(1 + p) = 18 is a primitive root mod 5^{e}, where e is any integer greater than one. Let us show that 18 is not a primitive root mod 5^{2003}. If it were so then powers of 18 would give us all the invertible elements mod 5^{2003}. Then the same would be true mod 25. However, 18 ≡ −7 mod 25, and (−7)^{4} ≡ 49^{2} ≡ (−1)^{2} ≡ 1 mod 25, hence the order of 18 mod 25 is 4, and not ϕ(25) = 20. The only remaining possibility is that 3 is a primitive root mod 5^{e} for any positive e.

12) (a) An easy check shows that if i, j ≥ 1 then n = 2^{i}3^{j} works.

(b) Let n be a solution, and write n = 2^{e}m with m odd. We know that n = 4ϕ(n) and so we see that e > 1. Now 2^{e}m = n = 4ϕ(n) = 4ϕ(2^{e})ϕ(m) = 2^{e+1}ϕ(m), and we deduce that m = 2ϕ(m), contradicting the fact that m is odd.

(c) Say t > 4 is an integer and n = ∏_{i} p_{i}^{e_{i}} is a solution to n = tϕ(n), with the p_{i} distinct primes. Then ∏_{i} p_{i} = t ∏_{i}(p_{i} − 1). However, I claim that there are no solutions to this equation if t > 4. This is because, if at least two of the p_{i} were odd, then at least two of the (p_{i} − 1) would be even, and hence the right hand side would be a multiple of 4, but the left hand side cannot be. We deduce that at most one of the p_{i} dividing n can be odd. So the choices for the set of all p_{i} dividing n are {2}, {p} or {2, p} where p is odd (note that n must be at least 2 and hence the set of all p_{i} cannot be empty). Working out t in each case gives t = 2, t = \frac{p}{p−1} = 1 + \frac{1}{p−1} and t = \frac{2p}{p−1} = 2 + \frac{2}{p−1}. If t is to be an integer in these last two cases, then p − 1 will have to divide 2, and so p = 3 and we check that in no cases do we get t > 4.

13^{∗}) (a) (2 marks) We have (p − 1)/2 = 3m. The first m values of ˜ −3j are −3, −6, …, −3m, these are visibly negative. The next m values are positive numbers 3m − 2, …, 1. The last m values are negative again. Thus r_{p}(−3) = 2m.

(b) (2 marks) This time (p − 1)/2 = 3m + 2. Now the first m values of ˜ −3j are negative, the next m + 1 are positive, and the last m + 1 are again negative. We obtain r_{p}(−3) = 2m + 1.

(c) (1 mark) (\frac{−3}{p}) = 1 iff p is congruent to 1 modulo 6.

(d) (3 marks) Assume there are only finitely many such primes, say p_{1}, …, p_{n}. Consider N = 12p_{1}^{2} … p_{n}^{2} + 1. If q is prime and q|N, then q is odd, and q is not a factor of 12p_{1}^{2} … p_{n}^{2} (in particular, q ≠ 3). We write −1 ≡ 3m^{2} mod q. Therefore, −3 is a quadratic residue mod q, whence q ≡ 1 mod 6.

14^{∗}) (2 marks) Let’s use the multiplicativity of the Legendre symbol. We have

(\frac{3}{p}) = (\frac{−3}{p}) × (\frac{−1}{p})

One symbol depends on p modulo 6, and the other on p modulo 4, so we consider the possibilities for p modulo 12. These are 1, 5, 7 and 11. In these cases (\frac{3}{p}) equals 1, −1, −1 and 1, respectively.

The corresponding values of (\frac{p}{3}) are 1, −1, 1 and −1. The ration is 1 if p is congruent to 1 mod 4, and −1 if it isn’t.

15) We have

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

Here 1/n is the inverse of n mod p. Note that n ↦ 1 + \frac{k}{n} is a bijection of (ℤ/p)^{∗} onto ℤ/p \ {1}. Since the number of non-zero quadratic residues equals the number of quadratic non-residues, and one residue, namely, 1 is missing in the last sum, the sum equals −1.