Systems of Linear Congruences—Multiple Moduli - Introduction to Cryptography with Java Applets - page 161

or that

u

1 (mod 7).
Again, rewrite this congruence as an equation; namely

u = 7 v + 1

which we can then substitute for x in the last congruence since

x = 20 u + 15 = 20(7 v + 1) + 15 = 140 v + 35.

Replace x with this expression in the last congruence

140 v + 35 5 v + 8 8 (mod 9)
to obtain solutions for v , which are all v such that

v 0 (mod 9).

Finally, rewrite this congruence as an equation

v = 9 w + 0.

x

Once we back substitute this value for , we get

x v w w

= 140 + 35 = 140(9 ) + 35 = 1260 + 35

or, written as a congruence,

x 35 (mod 1260).
These are exactly the solutions desired, for note that if x 35(mod 1260), we certainly
have all of the following:

x 35 3 (mod 4)
x 35 0 (mod 5)
x 35 0 (mod 7)
x 35 8 (mod 9).

8.1

THE CHINESE REMAINDER THEOREM
This method of solving these types of congruences is very effective, but we can develop an
even faster method of solving such systems if we only require that the moduli be pairwise
relatively prime. Note, however, that the previous method has no such requirement. The
proof of proposition 27 describes the new method; it is called the Chinese Remainder The-
orem, since the Chinese have known its results since ancient times. However, we must first
establish the two following facts:

PROPOSITION 25. Suppose integers a 1 , a 2 , . . . , a n are pairwise relatively prime. Then

( a 1 a 2 ... a n )| c if and only if a 1 | c , a 2 | c , . . . , a n | c .