Page 299 - Discrete Mathematics and Its Applications

278 4 / Number Theory and Cryptography

THEOREM 2 THE CHINESE REMAINDER THEOREM Let m 1 ,m 2 ,...,m n be pairwise relatively
prime positive integers greater than one and a 1 ,a 2 ,...,a n arbitrary integers. Then the system

x ≡ a 1 (mod m 1 ),
x ≡ a 2 (mod m 2 ),
·
·
·
x ≡ a n (mod m n )

has a unique solution modulo m = m 1 m 2 ··· m n . (That is, there is a solution x with
0 ≤ x< m, and all other solutions are congruent modulo m to this solution.)

Proof: To establish this theorem, we need to show that a solution exists and that it is unique
modulo m. We will show that a solution exists by describing a way to construct this solution;
showing that the solution is unique modulo m is Exercise 30.
To construct a simultaneous solution, first let

M k = m/m k

for k = 1, 2,...,n. That is, M k is the product of the moduli except for m k . Because m i and m k
have no common factors greater than 1 when i = k, it follows that gcd(m k ,M k ) = 1. Conse-
quently, by Theorem 1, we know that there is an integer y k , an inverse of M k modulo m k , such
that

M k y k ≡ 1 (mod m k ).

To construct a simultaneous solution, form the sum

x = a 1 M 1 y 1 + a 2 M 2 y 2 + ··· + a n M n y n .

We will now show that x is a simultaneous solution. First, note that because M j ≡ 0 (mod m k )
whenever j = k, all terms except the kth term in this sum are congruent to 0 modulo m k . Because
M k y k ≡ 1 (mod m k ) we see that

x ≡ a k M k y k ≡ a k (mod m k ),

for k = 1, 2,...,n. We have shown that x is a simultaneous solution to the n congruences.

Example 5 illustrates how to use the construction given in our proof of the Chinese remainder
theorem to solve a system of congruences. We will solve the system given in Example 4, arising
in Sun-Tsu’s puzzle.
EXAMPLE 5 To solve the system of congruences in Example 4, first let m = 3 · 5 · 7 = 105, M 1 = m/3 =
35,M 2 = m/5 = 21, and M 3 = m/7 = 15. We see that 2 is an inverse of M 1 = 35 modulo 3,
because 35 · 2 ≡ 2 · 2 ≡ 1 (mod 3); 1 is an inverse of M 2 = 21 modulo 5, because 21 ≡
1 (mod 5); and 1 is an inverse of M 3 = 15 (mod 7), because 15 ≡ 1 (mod 7). The solutions to
this system are those x such that

x ≡ a 1 M 1 y 1 + a 2 M 2 y 2 + a 3 M 3 y 3 = 2 · 35 · 2 + 3 · 21 · 1 + 2 · 15 · 1
= 233 ≡ 23 (mod 105).