M3/4P14 Elementary Number Theory Answers Sheet 1.

1) By the division algorithm, every integer is of the form 5n + a, where a is 0, 1, 2, 3 or 4. The square of this is 25n^{2} + 10an + a^{2}. Now note that a^{2} is 0, 1 or 4 plus a multiple of 5. Hence the same is true for 5(5n^{2} + 2an) + a^{2}.

2) Note that the answers for λ and μ are not unique.

54 = 1 × 30 + 24
30 = 1 × 24 + 6
24 = 4 × 6 + 0

so stop and return the answer 6. Now work backwards:

6 = 30 − 24
= 30 − (54 − 30) = 2 × 30 − 54

So λ = 2 and μ = −1 will do. Parts (b) and (c) are just as straightforward; 1 = (−1)a + 12345679b and 17 = 4 × 323 − 5 × 255.

3^{∗}) 3 marks. We know d divides a and b, so the fact that α and β are integers is obvious. Furthermore, we know that there are integers λ and μ such that d = λa+μb; dividing by d gives 1 = λα+μβ and hence hcf(α, β) = 1 by Corollary 1.7.

4) (a) Say λa + μb = d. If c = γd then x = γλ and y = γμ will do. On the other hand, if d does not divide c, then there can’t be any solutions to xa + yb = c in integers x and y, because d definitely divides xa + yb.

(b) An easy substitution shows that x = x_{0} + tb/d and y = y_{0} − ta/d is a solution. The heart of the question is hence showing that these are the only solutions. So let’s let x and y be a solution to xa + yb = c. We know that x_{0}a + y_{0}b = c and subtracting, we deduce that (x − x_{0})a + (y − y_{0})b = 0. Write a = αd and b = βd, and we deduce that (x − x_{0})α = β(y_{0} − y). But α and β are coprime by question 3, and hence by Corollary 1.8 we see that β divides x − x_{0} and α divides y_{0} − y. Because at least one of α and β are non-zero, we deduce that x − x_{0} = tβ and y_{0} − y = tα for some integer t, and this is what we wanted.

(c) x = y = 12 is a solution, and by the previous question, all solutions must be of the form x = 12 + 9t and y = 12 + 10t. To make these positive we must have −1 ≤ t and hence the general solution is x = 3 + 9u, y = 2 + 10u for any integer u ≥ 0 (u = t + 1).

5^{∗}) (a) 6 marks, if full details are given.

Assume for contradiction that there are only finitely many, say p_{1}, …, p_{n}. Then each p_{i}^{2} is congruent to 1 mod 3, hence p_{1}^{2} … p_{n}^{2} is also. Now p_{1}^{2} … p_{n}^{2}+1 is congruent to 2 mod 3. It is a product of primes. It is easy to see that 3 is not a factor. If all prime factors are 1 mod 3, then so is the product. Hence there is a prime factor p congruent to 2 mod 3. By assumption p must be one of p_{1}, …, p_{n}, and hence p|1. Contradiction.

(b) 2 marks. All primes that are 2 mod 3 are 5 modulo 6 (and never 2 modulo 6, which has 2 as a factor).

6^{∗}) 5 marks. Let us follow the proof of CRT. We have

b_{1} = 2, b_{2} = 3, b_{3} = 6, m_{1} = 3, m_{2} = 5, m_{3} = 7, n_{1} = 35, n_{2} = 21, n_{3} = 15.

We observe that 12 × 3 − 1 × 35 = 1, hence we can take k_{1} = −35. Next, (−4) × 5 + 1 × 21 = 1, so we set k_{2} = 21. Finally, (−2) × 7 + 1 × 15 = 1 implying that we can set k_{3} = 15. Now b_{1}k_{1}+b_{2}k_{2}+b_{3}k_{3} = −70+63+90 = 83 is a solution. The general solution is thus 83 + 105n, n ∈ ℤ.

7^{∗}) 4 marks. We know λa + μb = 1 for some integers λ and μ. Multiply by c and now observe that ab divides ac, ab divides cb and hence ab divides λac + μbc = c.