MODULE 2.
CONGRUENCE Exercises
2.8 Exercises
1. Find the last two digits of 3100 .
2. Find the last three digits of 79999 .
7
7···
3. Find the last digit of 77 where there are 1001 number of 7’s.
4. Show that 1982 divides 22222 · · · 222 (1980 2’s).
5. Find the smallest positive integer ending in 1986 divisible by 1987.
6. (i) Show that if 2n + 1 and 3n + 1 are both squares, then 40 divides n.
(ii) Show that if 3n + 1 and 4n + 1 are both squares, then 56 divides n.
7. Let a, b be integers. If a2 + b2 is divisible by 7, show that it is also divisible by 49.
8. Find all primes p such that p2 + 8 is also a prime.
9. Let p and q be two distinct primes. Show that pq divides pq−1 + q p−1 − 1.
10. Let p, q, r be three distinct odd primes such that r − 1 is a multiple of both p − 1
and q − 1. Show that 2q − 1 is divisible by pqr.
11. Show that
(1234)4321 + (4321)1234 ≡ 7 mod 11.
12. (i) Show that 4545 + 5454 is not a prime.
(ii) Show that n4 + 4n is never a prime for any integer n.
13. If 2p + 3p = an for any prime p, show that n = 1.
14. Show that 2(56!) + 1 is divisible by 59.
15. Let p be an odd prime. Show that
2 p−1
2.4. · · · .(p − 1) ≡ −(−1) 2 mod p.
16. If p is a prime of the form 4k + 1, show that the quadratic congruence x2 ≡
−1 mod p has a solution.
17. Show that 61! + 1 is divisible by 71.
18. Show that 63! + 24 is divisible by 73.
52
MODULE 2. CONGRUENCE Exercises
19. Find solutions of the following simultaneous congruences:
(A) x ≡ 2 mod 6, x ≡ −3 mod 7, x ≡ 5 mod 11.
(B) 4x ≡ 2 mod 6, 5x ≡ −3 mod 7, 3x ≡ 5 mod 11.
20. Find the smallest positive integer n such that it leaves remainder 1 when divided
by 11, 2 when divided by 12 and 3 when divided by 13.
21. Find the smallest positive integer n such that n is a multiple of 3, n+1 is a multiple
of 4, and n + 2 is a multiple of 5.
22. Find the smallest triple of consecutive integers n, n + 1 and n + 2 such that each
of them is not square-free.
23. Show that the linear congruences in two variables
ax + by ≡ w mod n
cx + dy ≡ z mod n
has a unique solution modulo n if and only if gcd(ad − bc, n) = 1.
24. Find solutions of the following simultaneous congruences:
(A) x ≡ 2 mod 6, x ≡ 4 mod 8, x ≡ 5 mod 9.
(B) x ≡ 1 mod 4, x ≡ 3 mod 6, x ≡ 6 mod 9.
25. Can you find a positive integer n such that it leaves remainder 2 when divided by
10, 3 when divided by 1 and 12 when divided by 13?
26. Find a solution x0 of 2x ≡ 5 mod 73 such that x0 ≡ −6 mod 72 .
27. Solve x3 + x − 68 ≡ 0 mod 53 .
53