MAS3008 NUMBER THEORY EXERCISE SHEET 1

This sheet does not count towards assessment (but subsequent sheets will). However, if you hand in your answers, they will get marked. Please put your work in the Coursework Box on Level 8 of the Laver Building by Friday 25th October.

1. For each pair a, b find d = gcd(a, b) and find integers x, y such that d = ax + by:

(i) a = 34, b = 20; (ii) a = 55, b = 34; (iii) a = 1105, b = 208.

2. Let a > b > 1, and let r_{i} denote the remainder in the ith division when applying the Euclidean Algorithm to compute gcd(a, b), with r_{0} = b, r_{−1} = a. (Thus, for i ≥ 1, in the ith division we divide r_{i−2} by r_{i−1}). Show that

r_{i+2} < \frac{1}{2}r_{i}

(provided that at least i+2 divisions are needed), and hence deduce that the number of divisions required to compute gcd(a, b) is less than 1 + 2 log_{2} b. [Hint: Consider separately the cases r_{i+1} ≤ \frac{1}{2}r_{i} and r_{i+1} > \frac{1}{2}r_{i}.]

3. Let a, b, n ∈ ℤ with gcd(a, n) = gcd(b, n) = 1. Prove that gcd(ab, n) = 1.

4. Let a, b ∈ ℕ and let d = gcd(a, b). Set l = ab/d. Show that l is least common multiple (lcm) of a and b in the sense that the following two properties hold:

(i) a | l and b | l; (ii) if a | m and b | m then l | m. (You might find Euler’s Lemma useful.) Show also that l is the unique positive integer with these properties.

5. Find the prime factorisations of the following numbers:

(i) 60 (ii) 105; (iii) 65536. For each of these numbers n, write down v_{p}(n) for all primes p. (Recall that v_{p}(n) means the integer e such that p^{e} | n but p^{e+1} ∤ n.)

6. Let n ≥ 1. Show that there exist n consecutive composite numbers. [Hint: Consider (n + 1)! + k for 2 ≤ k ≤ n + 1.] 7. Show that if n > 3 then

(i) n, n + 2 and n + 4 cannot all be prime; (ii) n, 2n + 1 and 4n + 1 cannot all be prime.

8. Let m, n, d ∈ ℕ.

(i) Show that v_{p}(mn) = v_{p}(m) + v_{p}(n) for all primes p. Show also that d | m ⇔ v_{p}(d) ≤ v_{p}(m) for all primes p.

(ii) Deduce that

d | m and d | n ⇔ v_{p}(d) ≤ min(v_{p}(m), v_{p}(n)) for all primes p,

and hence that

gcd(m, n) = ∏_{p∈ℙ}p^{min(v_{p}(m),v_{p}(n))}.

(iii) Find an expression for lcm(m, n) (see Question 4) similar to the expression for gcd(m, n) in (ii).

9. (This question illustrates that uniqueness of prime factorisations does require proof). Let H = {1, 5, 9, 13, …} be the set of all natural numbers of the form 4m+1.

(i) Show that H is closed under multiplication, that is, if h ∈ H and k ∈ H then hk ∈ H. Now call h ∈ H an H-prime if h > 1 but h cannot be written as a product of two smaller elements of H. Thus 9 is an H-prime but 45 = 5 × 9 isn’t. (ii) Show that if h ∈ H and h > 1 then h can be written as a product of H-primes. By considering the example h = 441, show that this factorisation into H-primes is not always unique (up to order of the factors). (iii) Explain why the argument used to show uniqueness in the proof of the Fundamental Theorem of Arithmetic doesn’t work for H-primes.

Nigel Byott October 2002