ASSIGNMENT 2 1. Solve the following linear congruences (you may if you wish, find some solutions by inspection): (a) 3x = 12 (mod 14), (b) 3x = 5 (mod 7), (c) 4x = 4 (mod 6), (d) 4x = 7 (mod 12). 2....

ASSIGNMENT 2 1. Solve the following linear congruences (you may if you wish, find some solutions by inspection): (a) 3x = 12 (mod 14), (b) 3x = 5 (mod 7), (c) 4x = 4 (mod 6), (d) 4x = 7 (mod 12). 2. Solve 403x = 62 (mod 527). (Hint: You may find the calculation you did in Assignment 1 Question 6 useful). 3. Use congruences to verify the divisibility statement 13 | (168129 + 1). 4. Solve x3-1 = 0 (mod 3). (Hint. Notice that the answer depends only on the residue class.) 5. Show that if a is an odd integer, then a2 = 1 (mod 8). 6. Find an inverse modulo 19 of each of the following integers. (a) 3, (b) 5, (c) 12. 7. Determine all the odd numbers which are divisible by 3. Deduce that, among any three successive odd numbers greater than or equal to 5, at least one is composite. 8. In the ISBN of a book the 5th digit is unreadable, so the number is 3-764?-5197-7. Recover the missing digit knowing that S10 k=1 kxk = 0 (mod 11) where xk is the k-th digit of the ISBN. 9. Set up a round-robin tournament schedule for (a) 7 teams, (b) 8 teams. 10. Assume {r1, . . . , rn} is a complete system modulo n. Show that, for any integer a, the set {r1 + a, . . . , rn + a} is also a complete system. Challenge problem1 If (m, n) = 1 and m = 3, n = 3, show that the congruence x2 = 1 (mod mn) has solutions other than x = ±1 (mod mn). (Hint. Prove that there exists x with x = 1 (mod m) and x = -1 (mod n). Show that such x ?= ±1 (mod mn).) Challenge problem Show that for any positive integer n there exists a number composed by 0’s and 1’s (in the decimal system) that is divisible by n. 1The challenge problems are harder and do not count for assessment