KMB, 18/10/99

M3/4P14 Elementary Number Theory—Problem Sheet 1

This is assessed coursework. Please hand in solutions to the starred questions (i.e., to questions 1, 2, 4, 5 and 6b) at the end of the lecture on Wednesday 27th October.

1^{∗}) For the s and t below, use Euclid’s algorithm to work out what hcf(s, t) is, and furthermore find integers λ and μ such that λs + μt = 1.

(a) s = 182, t = 221.

(b) s = −15, t = 24.

(c) s = 34, t = 21.

(Remark: Can you make an intelligent remark about what’s going on in part (c): for example, why do you think that this is, in some sense, the “worst possible” case for Euclid’s algorithm?)

2^{∗}) Let a and b be integers, not both zero, and let d be their highest common factor. Show (without using the fact that integers are uniquely the product of primes!) that any integer e that divides both a and b also divides d.

3) Let a, b and c be three positive integers (positivity isn’t necessary but I’ve just put it in to make the question slightly simpler). Define the highest common factor of a, b and c to be the largest positive integer d such that d divides all of a, b and c. Denote this integer by hcf(a, b, c).

a) Say one or two words about why d exists.

b) Prove carefully that hcf(a, b, c) = hcf(hcf(a, b), c). Hint: show that the set of integers that divide both hcf(a, b) and c is equal to the set of integers that divide all three of a, b and c.

c) Deduce that if the highest common factor of a, b and c is 1, then there are integers λ, μ and ν such that λa + μb + νc = 1.

d) Find three positive integers a, b and c such that hcf(a, b), hcf(b, c) and hcf(c, a) are all greater than 1, but hcf(a, b, c) = 1.

4^{∗}) I am thinking of two integers a and b, and I will tell you that there are integers λ and μ such that λa + μb = 9. What can you deduce about hcf(a, b)? More precisely, show that hcf(a, b) must be in some finite list of positive integers (that you are to determine), and for each of the entries t in the list, find integers a and b such that λ and μ exist, and hcf(a, b) = t.

5^{∗}) Let N be a huge positive integer. Prove that at some point the gap between two consecutive primes is at least N. More precisely, find a positive integer M such that none of M, M + 1, M + 2, …, M + (N − 1) are prime. [Hint: If you haven’t seen the trick before then one good place to find M might be in a book.]

6)

a) Let p_{n} denote the nth prime. Prove that p_{n} < 2^{2^{n}}. Hint: look at the argument which showed there were infinitely many primes.

b^{∗}) Show that in fact p_{n} ≤ 2^{2^{n−1}} + 1 (use Fermat numbers!).

(PTO)

a) Prove that there are infinitely many primes p of the form 4k − 1. Hint: if there were only finitely many, multiply them together, square, and add two.

b) Try to prove that there are infinitely many primes p which end in a 9 (i.e., are of the form 10k +9) using this method. What goes wrong? [Hint: if nothing goes wrong, then either you are very smart or your answer to (a) is probably wrong]. Guess whether there are infinitely many primes which end in 9. Guess whether there are infinitely many primes which end in 999999999.