MAS3008 NUMBER THEORY EXERCISE SHEET 2

The following questions, or parts of questions, count for assessment: 1(i)(iii)(iv), 2(ii)(iv), 3, 5, 7, 9, 10(i)(iv)(v), 11(ii)(iii). These are marked *. Please hand in your solutions, via the Coursework Box on Level 8 of the Laver Building, by Friday 15th November.

1. Solve the following congruences (giving the most general solution), or show that no solution exists:

(i)* 3x ≡ 10 (mod 13);

(ii) 12x ≡ 20 (mod 38);

(iii)* 15x ≡ 43 (mod 99);

(iv)* 66x ≡ 102 (mod 168);

(v) 553x ≡ 490 (mod 1001). [10]

2. Find all integer solutions (if any exist) to each of the following equations: (i) 7x − 11y = 4; (ii)* 13x + 31y = 2; (iii) 15x − 27y = 5; (iv)* 12x + 28y = 16. [10]

3*. (i) Show that any natural number n with n ≡ 3 (mod 4) must have at least one prime factor q ≡ 3 (mod 4). [3] (ii) Deduce that there are infinitely many primes q ≡ 3 (mod 4). [Hint: If p_{1}, p_{2}, …, p_{r} is any finite list of primes, what can you say about the prime factors of N = 4p_{1}p_{2} … p_{r} − 1?] [7] (iii) Adapt parts (i) and (ii) to show that there are infinitely many primes q ≡ 5 (mod 6). [5]

Total for question: [15]

4. Show that the property

ab = 0 ⇒ a = 0 or b = 0

holds in ℤ_{n} if and only if n is a prime number.

5*. (i) Let n and k be integers ≥ 2. Show that (n − 1) | (n^{k} − 1). [3] (ii) Deduce that if n^{k} − 1 is prime then n = 2 and k is prime. [Hint: If k = ab you can apply (i) with n = 2^{a}.] [7] (iii) Which of the numbers M_{p} = 2^{p} − 1, for p = 2, 3, 5, 7, 11, are prime? [5] (iv)Primes of this form are called Mersenne primes. The largest known prime (discovered November 2001) is the Mersenne prime M_{p} for p = 13466917. How many decimal digits does this have? [5]

Total for question: [20] 6. Show that if k > 1 is odd then (n + 1) | (n^{k} + 1) for every natural number n. Show that if 2^{k} + 1 is prime then k = 2^{m} for some m ≥ 0. Verify that the numbers F_{k} = 2^{2^{k}} + 1 are prime for k = 0, 1, 2, 3, 4 but that F_{5} is divisible by 641. (Primes of this form are called Fermat primes.)

7*. (i) Use Fermat’s Little Theorem to evaluate

(a) 2^{302} mod 7; (b) 5^{123} mod 61. [4] (ii) Let a be an integer with gcd(a, 561) = 1. Show that a^{560} ≡ 1 (mod p) for each of the primes p = 3, 11, 17, and hence that a^{560} ≡ 1 (mod 561).

[6]

Total for question: [10]

8. Recall that the order of a mod p is the smallest positive integer k with a^{k} ≡ 1 (mod p). Make a table of the orders of all integers 1 ≤ a ≤ 12 mod 13. Also, find the inverse in ℤ_{13} of each a, and compare the order of a mod 13 with the order of its inverse. What do you notice? Can you prove that this holds in general (i.e for any prime p in place of 13)?

9*. Let p be prime, let a ∈ ℤ, and let l be any prime which divides a^{p−1} + a^{p−2} + … + a + 1. Show that the order of a modulo l is either 1 or p. Deduce that either l = p or l ≡ 1 (mod p). Hence show that there are infinitely many primes l with l ≡ 1 (mod p). [15]

10. Solve each of the following systems of simultaneous congruences: (i)* x ≡ 6 (mod 17), x ≡ 5 (mod 11); (ii) x ≡ 3 (mod 9), 3x ≡ 10 (mod 17); (iii) 2x ≡ 1 (mod 9), 3x ≡ 5 (mod 17); (iv)* x ≡ 4 (mod 12), x ≡ 7 (mod 15);

(v)* x ≡ 1 (mod 5),  x ≡ 3 (mod 7),  x ≡ 2 (mod 9). [10]

11. Use the Chinese Remainder Theorem to find all solutions of the following congruences:

(i) x^{2} ≡ 1 (mod 77);

(ii)* x^{2} ≡ −1 (mod 65);

(iii)* x^{2} ≡ 1 (mod 165). [10]

Nigel Byott, October 2002