M3/4P14 Elementary Number Theory Problem Sheet 2.

This is assessed coursework. Please hand in solutions to the starred questions (i.e., to questions 1, 2, 3, 4) at the end of the lecture on Thursday the 13th of November.

1^{∗}) (a) How many elements does (ℤ/36)^{∗} have? For each element of (ℤ/36)^{∗}, find its inverse (using any method you like).

(b) What is the solution to 11x ≡ 7 mod 36?

2^{∗}) (a) Find all pairs of integers (m, n) for which the congruences x ≡ m mod 12 and x ≡ n mod 14 have a common solution.

(b) A common solution, if it exists, is unique modulo a certain integer M. Find this M.

Justify your answers.

3^{∗}) (a) Evaluate ϕ(332), ϕ(333), ϕ(334) and ϕ(335).

(b) Prove that ϕ(n) is even if and only if n ≥ 3.

4^{∗}) Find all positive integers n such that ϕ(n) is not a multiple of 3.

5) When do the congruences x ≡ a mod m and x ≡ b mod n have a common solution? Find a positive integer M such that a solution, if one exists, is unique modulo M.

6) Prove that if 0 ≤ n < m then the Fermat numbers 2^{2^{n}} + 1 and 2^{2^{m}} + 1 are coprime. Deduce another proof that there are infinitely many primes.

7) Let f and g be functions ℤ_{>0} → ℤ. Define a new function f ∗ g by

(f ∗ g)(n) = ∑_{d|n} f(d)g(n/d),

where the sum is, as usual, over the positive divisors of n. Prove that if f and g are multiplicative, then f ∗ g is also multiplicative. (The function f ∗ g is called the convolution of f and g.)

8) Prove that for all integers n we have n^{5} ≡ n mod 30. (Hint: work mod 2, 3 and 5 separately).

9) Show that 19x^{2} − 98y^{2} = 2003 has no integer solutions. (Hint: work modulo some small prime.)