Assignment 3

Problems 4.4 1. Solve the following linear congruence: (e) 34 x ≡ 60(mod 98) (f) 140 x ≡ 133(mod 301) (Hint: gcd(140,301) = 7 ) 2. Using congruence, solve the Diophantine equations below: (c) 5 x − 53 y ≡ 17 4. Solve each of the following sets of simultaneous congruence: (c) x ≡ 5(mod 6), x ≡ 4(mod11), x ≡ 3(mod17) . 11. Prove that the congruence: x ≡ a(mod n) and x ≡ b(mod m) admit a simultaneous solution if and only if gcd(n, m) a − b ; If a solution exists, confirm that it is unique modulo lcm(n, m) . Problems 5.2 12 n + 6 +1. 3. From Fermat’s theorem deduce that, for any integer n ≥ 0, 1311 10. Assuming that a and b are integers not divisible by the prime p , establish the following: (a) If a p ≡ b p (mod p), then a ≡ b(mod p) (b) If a p ≡ b p (mod p), then a p ≡ b p (mod p 2 ) (There’s a “Hint” in the textbook following the question.) 11. Employ Fermat’s theorem to prove that, if p is an odd prime, then (a) 1 p −1 + 2 2− p +  ( p − 1) p −1 ≡ −1(mod p ) (b) 1 p + 2 2 +  ( p − 1) p ≡ 0(mod p) (There’s a “Hint” in the textbook following the question) 15 Establish the statements below: p (a) If the number M p = 2 − 1 is composite, where p is a prime, then M p is a pseudo prime. n (b) Every composite number Fn = 2 2 + 1 is a pseudo prime. (n = 0,1,2 ) n

n +1 2 2 (Hint: By Question 21 of Section 2.3, 2 2 implies that 2

Fn 2 2

n +1

n +1

− 1 2 Fn −1 − 1; but

− 1;

Problems 5.3 5. (a) Prove that an integer n > 1 is prime if and only if (n − 2)!≡ 1(mod n) . (b) If n is a composite integer, show that (n − 1)!≡ 0(mod n), except when n = 4 .