M3/4P14 Elementary Number Theory Problem Sheet 1.

This is assessed coursework. Please hand in solutions to the starred questions (i.e., to questions 3, 5, 6, 7) at the end of the lecture on Wednesday the 29th of October.

1) Use the division algorithm to prove that the square of any integer is of the form 5k, 5k + 1 or 5k + 4 for some k ∈ ℤ.

2) (M1F revision). For each pair (a, b) of integers below, find the highest common factor d of a and b, and also find integers λ and μ such that λa+μb = d.

(a) a = 30, b = 54

(b) a = 123456789, b = 10

(c) a = 323, b = 255.

3^{∗}) Let a and b be integers, not both 0, and set d = hcf(a, b). Prove that if a = αd and b = βd, then α and β are coprime integers.

4) For fixed integers a, b and c, with a and b not both 0, we show in this question how to find all integer solutions x and y to the equation

xa + yb = c.

(a) If d = hcf(a, b), then prove that there are integers x and y such that xa + yb = c if and only if d divides c.

(b) Assume that d divides c, so there are integer solutions to the equation. Say x = x_{0} and y = y_{0} is one integer solution. Prove that the general integer solution is x = x_{0} + tb/d and y = y_{0} − ta/d, as t runs through the integers.

(c) Find all solutions in positive integers x and y to the equation

10x − 9y = 12.

5^{∗}) (a) Prove that there are infinitely many primes of the form 2 + 3k, where k is an integer.

(b) Deduce that there are infinitely many primes of the form 5+6k, where k is an integer.

6^{∗}) Find all integers x satisfying the system of congruences:

x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 6 mod 7.

7^{∗}) Prove, without assuming that every integer is uniquely the product of primes, that if a and b are coprime integers, and a|c and b|c, then ab|c.