Page 306 - Discrete Mathematics and Its Applications

4.4 Solving Congruences 285

12. Solve each of these congruences using the modular in- 20. UsetheconstructionintheproofoftheChineseremainder
verses found in parts (b), (c), and (d) of Exercise 6. theorem to find all solutions to the system of congruences
a) 34x ≡ 77 (mod 89) x ≡ 2 (mod 3), x ≡ 1 (mod 4), and x ≡ 3 (mod 5).
b) 144x ≡ 4 (mod 233) 21. Use the construction in the proof of the Chinese remain-
c) 200x ≡ 13 (mod 1001) der theorem to find all solutions to the system of congru-
2
13. Find the solutions of the congruence 15x + 19x ≡ 5 ences x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5), and
(mod 11). [Hint: Show the congruence is equivalent to x ≡ 4 (mod 11).
2
thecongruence15x + 19x + 6 ≡ 0 (mod11).Factorthe 22. Solve the system of congruence x ≡ 3 (mod 6) and
left-hand side of the congruence; show that a solution of x ≡ 4 (mod 7) using the method of back substitution.
the quadratic congruence is a solution of one of the two 23. Solve the system of congruences in Exercise 20 using the
different linear congruences.] method of back substitution.
2
14. Find the solutions of the congruence 12x + 25x ≡ 24. Solve the system of congruences in Exercise 21 using the
10 (mod 11). [Hint: Show the congruence is equivalence method of back substitution.
2
to the congruence 12x + 25x + 12 ≡ 0 (mod 11). Fac- 25. Write out in pseudocode an algorithm for solving a si-
tor the left-hand side of the congruence; show that a so- multaneous system of linear congruences based on the
lution of the quadratic congruence is a solution of one of construction in the proof of the Chinese remainder theo-
two different linear congruences.]
rem.
∗ 15. Show that if m is an integer greater than 1 and ac ≡ ∗ 26. Find all solutions, if any, to the system of congruences
bc (mod m), then a ≡ b(mod m/gcd(c, m)).
x ≡ 5 (mod 6), x ≡ 3 (mod 10), and x ≡ 8 (mod 15).
16. a) Show that the positive integers less than 11, except ∗ 27. Find all solutions, if any, to the system of congruences
1 and 10, can be split into pairs of integers such that x ≡ 7 (mod 9), x ≡ 4 (mod 12), and x ≡ 16 (mod 21).
each pair consists of integers that are inverses of each
other modulo 11. 28. Use the Chinese remainder theorem to show that an
integer a, with 0 ≤ a< m = m 1 m 2 ··· m n , where the
b) Use part (a) to show that 10!≡−1 (mod 11).
positive integers m 1 ,m 2 ,...,m n are pairwise relatively
2
17. Show that if p is prime, the only solutions of x ≡ prime, can be represented uniquely by the n-tuple
1 (mod p) are integers x such that x ≡ 1 (mod p) or (a mod m 1 , a mod m 2 ,...,a mod m n ).
x ≡−1 (mod p).
∗ 29. Let m 1 ,m 2 ,...,m n be pairwise relatively prime integers
∗ 18. a) Generalize the result in part (a) of Exercise 16; that greater than or equal to 2. Show that if a ≡ b(mod m i )
is, show that if p is a prime, the positive integers less for i = 1, 2,...,n, then a ≡ b(mod m), where m =
than p, except 1 and p − 1, can be split into (p − 3)/2 m 1 m 2 ··· m n . (This result will be used in Exercise 30
pairs of integers such that each pair consists of inte- to prove the Chinese remainder theorem. Consequently,
gers that are inverses of each other. [Hint: Use the do not use the Chinese remainder theorem to prove it.)
result of Exercise 17.] ∗ 30. Complete the proof of the Chinese remainder theorem
b) From part (a) conclude that (p − 1)!≡−1 (mod p) by showing that the simultaneous solution of a system
whenever p is prime. This result is known asWilson’s of linear congruences modulo pairwise relatively prime
theorem.
moduli is unique modulo the product of these moduli.
c) What can we conclude if n is a positive integer such [Hint: Assume that x and y are two simultaneous solu-
that (n − 1)! ≡−1 (mod n)? tions. Show that m i | x − y for all i. Using Exercise 29,
∗ 19. This exercise outlines a proof of Fermat’s little theorem. conclude that m = m 1 m 2 ··· m n | x − y.]
a) Suppose that a is not divisible by the prime p. Show 31. Which integers leave a remainder of 1 when divided by 2
that no two of the integers 1 · a, 2 · a,..., (p − 1)a and also leave a remainder of 1 when divided by 3?
are congruent modulo p. 32. Which integers are divisible by 5 but leave a remainder
b) Conclude from part (a) that the product of of 1 when divided by 3?
1, 2,...,p − 1 is congruent modulo p to the prod- 33. Use Fermat’s little theorem to find 7 121 mod 13.
uct of a, 2a,..., (p − 1)a. Use this to show that
34. Use Fermat’s little theorem to find 23 1002 mod 41.
(p − 1)!≡ a p−1 (p − 1)! (mod p). 35. Use Fermat’s little theorem to show that if p is prime and
p | a, then a p−2 is an inverse of a modulo p.
c) Use Theorem 7 of Section 4.3 to show from part (b) 36. Use Exercise 35 to find an inverse of 5 modulo 41.
that a p−1 ≡ 1 (mod p) if p | a.[Hint: Use Lemma 3 37. a) Show that 2 340 ≡ 1 (mod 11) by Fermat’s little theo-
10 34
of Section 4.3 to show that p does not divide (p − 1)! rem and noting that 2 340 = (2 ) .
and then use Theorem 7 of Section 4.3. Alternatively, b) Show that 2 340 ≡ 1 (mod 31) using the fact that
5 68
68
use Wilson’s theorem from Exercise 18(b).] 2 340 = (2 ) = 32 .
p
d) Use part (c) to show that a ≡ a(mod p) for all in- c) Conclude from parts (a) and (b) that 2 340 ≡
tegers a. 1 (mod 341).