174 7. ANCIENT NUMBER THEORYthat any number of such congruences can be solved simultaneously if the divisors
are all pairwise relatively prime is the content of what we know now as the Chinese
remainder theorem. According to Dickson, (1920, p. 57) this name arose when the
mathematically astute British missionary Alexander Wylie (1815-1887) wrote an
article on it in the English-language newspaper North China Herald in 1852. By
that time the result was already known in Europe, having been discovered by Gauss
and published in his Disquisitiones arithmetics (Art. 36) in 1836.
Sun Zi's answer to this problem shows that he knew a general method of pro-
ceeding. He says, "Since the remainder on division by 3 is 2, take 140. The
remainder on division by 5 is 3, so take 63. The remainder on division by 7 is 2,
so take 30. Add these numbers, getting 233. From this subtract 210, getting the
answer as 23."
It is just possible that the reader may not discern the underlying reasoning here,
and so a bit of explanation may help. Sun Zi reasons that all multiples of 35 = 7 • 5
will leave a remainder of zero when divided by 5 or 7. He therefore took a multiple
of 35, 140 = 35-4, that leaves a remainder of 2 when divided by 3. One may well
ask why he didn't simply take 35 itself, since it also leaves a remainder of 2 when
divided by 3. The seemingly clumsy use of 140 instead reveals still more of Sun
Zi's thought processes. He must have looked first for a multiple of 35 that leaves
a remainder of 1 when divided by 3, found it to be 70, then multiplied it by 2.^9
Similarly, 63 is the smallest multiple of 21 = 7 · 3 that leaves a remainder of 3 when
divided by 5, and 30 is the smallest multiple of 15 = 3-5 that leaves a remainder of 2
when divided by 7. Adding all three numbers, we get the number 233, which leaves
the desired remainders on all three divisions. Sun Zi also knew that any multiple of
105 = 3-5-7 could be added or subtracted without affecting any of the remainders.
Hence subtracting 210 produced the smallest possible solution. It is obvious from
this explanation that Sun Zi's method is perfectly general and can be used to find
all possible solutions to such problems. What is concealed in his exposition is the
general hypothesis that the divisors must be pairwise relatively prime. Sun Zi does
not discuss this concept, but obviously he must have encountered cases where such
problems cannot be solved. Almost certainly he would have traced the difficulty
back to the existence of common factors among the divisors.
The importance of this kind of problem to the Chinese was not merely the-
oretical. Given that the ratio of a month—the time between two successive full
moons—to a year is 19:235, questions involving calendars lead very often to find-
ing numbers that leave a given remainder when divided by 19 and another given
remainder when divided by 235. For example, suppose we know that the moon was
full on June 1, 1996. What is the next year on which it will be full on June 4? (See
Problem 7.10.)
The secret of solving problems of this sort is the Euclidean algorithm. This
algorithm was known in China from the first century CE (see Shen, 1988) and
used to solve a variety of problems, including the conversion of a long decimal
expansion into a common fraction approximation with a small denominator (see
Problem 7.12).
(^9) We can assume that Sun Zi found 70 by trial and error. The appropriate multiple would not be
so easy if the divisors involved had seven digits each. A method for handling such harder cases
was discovered by the Hindus and is discussed below.