NUMBERS AND SETS EXAMPLES SHEET 3. W. T. G.

1. Solve (ie., find all solutions of) the equations (i) 7x ≡ 77 (mod 40). (ii) 12y ≡ 30 (mod 54). (iii) 3z ≡ 2 (mod 17) and 4z ≡ 3 (mod 19).

2. Without using a calculator, work out the value of 17^{10,000} (mod 31).

3. Again without using a calculator, explain why 23 cannot divide 10^{881} − 1.

4. Let a_{1} = 6 and for n > 1 let a_{n} = 6^{a_{n−1}}. What is a_{2002} (mod 91)?

5. An RSA encryption scheme (n, d) has modulus n = 187 and coding exponent d = 7. Factorize n, and hence find a suitable decoding exponent e. If you have a calculator, check your answer by encoding the number 35 and then decoding the result.

6. Let p be a prime number and let 1 ⩽ k < p. Prove that \binom{p}{k} is a multiple of p. If you use any results from the course, make clear what they are and how you are using them.

7. Let P be a polynomial of the form P (x) = x^{d} + a_{d−1}x^{d−1} + … + a_{1}x + a_{0} ,

where the coefficients a_{i} are all integers. Suppose that r and s are coprime positive integers and that P (r/s) = 0. Prove that s = 1, again making clear what results you use in the process. Deduce that every root of P is either an integer or an irrational number.

8. Let p be a prime and let ℤ_{p}^{∗} stand for the set of non-zero integers mod p. Let a ∈ ℤ_{p}^{∗}. Prove that the function f defined by f(x) = ax is a bijection from ℤ_{p}^{∗} to itself. By considering the product f(1)f(2) … f(p − 1) give another proof of Fermat’s little theorem. Adapt your argument to prove Euler’s theorem as well.

9. Let a and b be positive integers with (a, b) = 1. Prove that ϕ(ab) = ϕ(a)ϕ(b). (This should be done from first principles - i.e., without using the fundamental theorem of arithmetic or the calculation of ϕ given in lectures.) Show that this gives another way to establish the value of ϕ(m), given the prime factorization of m.

10. Let p be an odd prime. An element x ≠ 0 of ℤ_{p} is a quadratic residue if it is a square - that is, if there exists y ∈ ℤ_{p} such that y^{2} = x. Prove that exactly (p − 1)/2 elements of ℤ_{p} are quadratic residues.

11. Let p be an odd prime. Deduce from Wilson’s theorem that −1 is a quadratic residue mod p if p is of the form 4n + 1. Prove that −1 is not a quadratic residue mod p if p is of the form 4n + 3.

12. Prove that x is a quadratic residue mod p if and only if x^{(p−1)/2} ≡ 1 (mod p). (This gives a second proof of the result of 10.)

13. Let p be a prime of the form 3k + 2. Show that the only solution to x^{3} = 1 in ℤ_{p} is x = 1. Deduce, or prove directly, that every element of ℤ_{p} has a cube root.

14. By considering numbers of the form (2p_{1}p_{2} … p_{k})^{2} + 1, prove that there are infinitely many primes of the form 4n + 1.

15. Show that 19^{19} is not the sum of a fourth power and a (positive or negative) cube.

16. Let n ≥ 2 be a positive integer such that we have a^{n−1} ≡ 1 (n) for every a coprime to n. Must n be prime?

17. (Not hard, but optional.) Prove that addition of positive integers is associative, and prove the cancellation law for addition (a + c = b + c implies that a = b), starting from the Peano axioms.