Chinese Remainder Theorem
An old Chinese riddle asks the following question.
Is there a positive integer x such that when x is divided by 3 it yields a remainder 2, when x is divided by 5 it yields a remainder 4, and when x is divided by 7 it yields a remainder 6?
In other words, we seek a common solution of the following three congruence equations:
x ≡ 2 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7)
Observe that the moduli 3, 5, and 7 are pairwise relatively prime. (Moduli is the plural of modulus.) Thus the following theorem (proved in Problem 11.60) applies; it tells us that there is a unique solution modulo:
M = 3 · 5 · 7 = 105.
Theorem 11.29 (Chinese Remainder Theorem): Consider the system
x ≡ r1 (mod m1), x ≡ r2 (mod m2), · · ·, x≡ rk (mod mk) (11.8)
where the mi are pairwise relatively prime. Then the system has a unique solution modulo:
M = m1m2 · · ·mk.
One can actually give an explicit formula for the solution of the system (11.8) in Theorem 11.29 which we state as a proposition.
Proposition 11.30: Consider the system (11.8) of congruence equations. Let M = m1m2 . . . mk, and:
(Then each pair Mi and mi are co-prime.) Let s1, s2, . . . , sk be the solutions respectively, of the congruence equations
M1x ≡ 1 (mod m1), M2x ≡ 1 (mod m2), …, Mkx ≡ 1 (mod mk)
Then the following is a solution of the system (11.8):
x0 = M1s1r1 +M2s2r2 +· · ·+Mkskrk (11.9)
We now solve the original riddle in two ways.
Method 1: First we apply the Chinese Remainder Theorem (CRT) to the first two equations,
(a) x ≡ 2 (mod 3) and (b) x ≡ 4 (mod 5)
CRT tells us there is a unique solution modulo M = 3 · 5 = 15. Adding multiples of the modulus m = 5 to the given solution x = 4 of the second equation (b), we obtain the following three solutions of (b) which are less than 15:
4, 9, 14
Testing each of these solutions in equation (a), we find that 14 is the only solution of both equations. Now we apply the same process to the two equations
(c) x ≡ 14 (mod 15) and (d) x ≡ 6 (mod 7)
CRT tells us there is a unique solution modulo M = 15 · 7 = 105 . Adding multiples of the modulus m = 15 to the given solution x = 14 of the first equation (c), we obtain the following seven solutions of (b) which are less than 105:
14, 29, 44, 59, 74, 89, 104
Testing each of these solutions of (c) in the second equation (d) we find that 104 is the only solution of both equations. Thus the smallest positive integer satisfying all three equations is
x = 104
This is the solution of the riddle.
Method 2: Using the above notation, we obtain
M = 3 · 5 · 7 = 105, M1 = 105/3 = 35,
M2 = 105/5 = 21, M3 = 105/7 = 15
We now seek solutions to the equations:
35x ≡ 1 (mod 3), 21x ≡ 1 (mod 5), 15x ≡ 1 (mod 7)
Reducing 35 modulo 3, reducing 21 modulo 5, and reducing 15 modulo 7, yields the system:
2x ≡ 1 (mod 3), x ≡ 1 (mod 5), x ≡ 1 (mod 7)
The solutions of these three equations are, respectively,
s1 = 2, s2 = 1, s3 = 1
We now substitute into the formula (11.9) to obtain the following solution of our original system:
x0 = 35 · 2 · 2 + 21 · 1 · 4 + 15 · 1 · 6 = 314
Dividing this solution by the modulus M = 105, we obtain the remainder
x = 104
which is the unique solution of the riddle between 0 and 105.
Remark: The above solutions s1 = 2, s2 = 1, s3 = 1 were obtained by inspection. If the moduli are large, we can always use the Euclidean algorithm to find such solutions as in Example 11.17.
“Sumber Informasi”
Thanks for reading Chinese Remainder Theorem. Please share...!
