Show your working and give full explanations for all questions.
1. Are the following statements true or false? For each, explain why.
(a) 4 divides 16
(b) 13 ≡ 24 (mod 6)
(c) 12 divides 3
(d) For any positive integer n 6= 13, gcd(13,n) = 1.
(e) If x is an integer such that 3x ≡ 6 (mod 9), then definitely x ≡ 2 (mod 9).
(f) There are integers x, y and z such that 14 divides 2x × 3y × 5z.
2. Let x and y be integers such that x ≡ 5 (mod 8) and y ≡ 3 (mod 8). Find the integer z such that 0 6 z 6 7 and 68x + 2y2 ≡ z (mod 8).
3. Use the extended Euclidean algorithm to find an integer x such that 127x ≡ 1 (mod 545).
