282 PROPERTIES OF THE INTEGERS [CHAP. 11
Proposition 11.30: Consider the system (11.8) of congruence equations. LetM=m 1 m 2 ...mk, and
M 1 =M
m 1,M 2 =M
m 2, ..., Mk=M
mk(Then each pairMiandmiare co-prime.) Lets 1 ,s 2 ,...,skbe the solutions respectively,
of the congruence equationsM 1 x≡ 1 (modm 1 ), M 2 x≡ 1 (modm 2 ),..., Mkx≡ 1 (modmk)Then the following is a solution of the system (11.8):x 0 =M 1 s 1 r 1 +M 2 s 2 r 2 +···+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 moduloM= 3 · 5 =15. Adding multiples of the modulusm=5tothe
given solutionx=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 moduloM= 15 · 7 =105. Adding multiples of the modulusm=15 to
the given solutionx=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 , 104Testing 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= 104This is the solution of the riddle.
Method 2:Using the above notation, we obtain
M= 3 · 5 · 7 = 105 ,M 1 = 105 / 3 = 35 ,M 2 = 105 / 5 = 21 ,M 3 = 105 / 7 = 15We now seek solutions to the equations
35 x≡ 1 (mod 3), 21 x≡ 1 (mod 5), 15 x≡ 1 (mod 7)Reducing 35 modulo 3, reducing 21 modulo 5, and reducing 15 modulo 7, yields the system2 x≡ 1 (mod 3), x≡ 1 (mod 5), x≡ 1 (mod 7)The solutions of these three equations are, respectively,
s 1 = 2 ,s 2 = 1 ,s 3 = 1