M3/4P14 Elementary Number Theory Answers Sheet 2.

1^{∗}) (3 marks)

(a) |(ℤ/36)^{∗}| = ϕ(36) = ϕ(4)ϕ(9) = 12. (1 mark) The elements are ±n, where n = 1, 5, 7, 11, 13, 17. The inverses are

1, −7, −5, −13, −11, 17. (1 mark)

(b) x ≡ −13 × 7 ≡ 17 mod 36 (1 mark)

2^{∗}) (5 marks)

(a) If m and n do not have the same parity, then there are obviously no solutions. If m and n are both even or both odd, write n − m = 2k = 14k − 12k, then n − 14k = m − 12k is a solution. (3 marks)

(b) The difference of two common solutions is a multiple of 12 and of 14, thus it is a multiple of 84. Conversely, if x is a solution, then x + 84k, k ∈ ℤ, is also. Hence a solution, if exists, is unique modulo 84. (2 marks)

3^{∗}) (7 marks)

(a) (1 mark for each computation)

ϕ(332) = ϕ(2^{2})ϕ(83) = 2 × 82 = 164,
ϕ(333) = ϕ(3^{2})ϕ(37) = 6 × 36 = 216,
ϕ(334) = ϕ(2)ϕ(167) = 166,
ϕ(335) = ϕ(5)ϕ(67) = 4 × 66 = 264.

(b) (3 marks) ϕ(2) = 1, so let n ≥ 3. Then either 4|n, or p|n, where p is an odd prime. In the first case ϕ(n) is divisible by ϕ(2^{s}) = 2^{s−1}, s ≥ 2. In the second case ϕ(n) is divisible by ϕ(p^{r}) = (p − 1)p^{r−1}, r ≥ 1, and that number is even.

4^{∗}) (5 marks) The prime factors can be of three possible types:

(1) p = 3; (2) p = 3k + 1; (3) p = 3k + 2. Since ϕ(p^{s}) = (p − 1)p^{s−1} for s > 0 we see that

(1) if 3^{s}|n for s > 0, then s = 1.

(2) no prime of the form 3k + 1 divides n. Hence n is a product of primes of the form 3k + 2 or 3 times such a

product. Conversely, any such n works.

Hints/solutions for non-assessed problems.

5) Let r = hcf(m, n), s = mn/r (this number is the lowest common multiple of m and n). A common solution should clearly satisfy the congruences x ≡ a mod r and x ≡ b mod r, so a necessary condition for solubility is that a ≡ b mod r. Let’s show that it is also suficient. Write r = λm + μn. We have a − b = kr = kλm + kμn. Now x = a − kλm = b + kμn is a common solution. If y is another common solution, then x − y is a multiple of m and n. This happens if and only if x − y is a multiple of s. Thus M = s.

6) First note that for t ∈ ℤ_{≥1} we have x^{2t} − 1 = (x + 1)(x − 1)(1 + x^{2} + x^{4} + … + x^{2t−2}). Hence if m is an integer then m + 1 divides m^{2t} − 1.

Substitute x = 2^{2^{n}} and we see that 2^{2^{n}} + 1 divides 2^{2^{n+1}t} − 1 for all t ≥ 1. Setting t = 2^{m−n−1} ≥ 1 we deduce 2^{2^{n}} +1 divides 2^{2^{m}} −1. Hence if an integer d divided 2^{2^{n}} + 1 it would divide 2^{2^{m}} − 1. If it also divided 2^{2^{m}} + 1 then it would divide their difference, which is 2. Hence it would divide 2^{2^{n}} and hence it would divide 1. So the highest common factor of 2^{2^{n}} + 1 and 2^{2^{m}} + 1 is 1, that is, these numbers are coprime.

Hence there must be infinitely many primes because 2^{2^{n}} + 1 > 1 for all n ≥ 0 and, as n varies, the prime factorisations of these infinitely many numbers will never have any primes in common.

7) Imitate the proof of Proposition 4.2 from the lectures.

9) Work modulo 7.