The story of the Chinese remainder theorem begins… in China, in the form of puzzles. The following puzzle is by the mathematician and astronomer Sun Zi, who lived between the 3rd and 5th centuries CE (and should not be confused with the general Sun Zi):
> "When General Han Xing lines up his soldiers in threes, two are left over; when he lines them up in fives, three are left over; and when he lines them up in sevens, two are left over. How many soldiers are there in Han Xing’s army?"
Behind its playful guise lies an arithmetic problem involving divisibility. Without solving it yet, we can observe that if it has one solution, adding 105 soldiers gives another, since 105 is a multiple of 3, 5 and 7. Repeating this process produces infinitely many solutions. It follows that if a solution exists, there is one between 1 and 105. In principle, this solves the puzzle: we need only try finitely many values!
However, this approach is tedious and sheds little light on the problem. It is better to deal with the three conditions separately. For two soldiers to be left over when they are grouped in threes, the total must be one of the numbers 2, 5, 8, 11, 14, 17, 20, 23, 26, 29… For three to be left over when they are grouped in fives, the total must be one of the numbers 3, 8, 13, 18, 23, 28… Finally, for two to be left over when they are lined up in sevens, the total must be one of the numbers 2, 9, 16, 23, 30… The number 23 belongs to all three sequences, so it is a solution to the problem—and the smallest one.
The others are 128, then 233, and so on, adding 105 each time. This approach is already clearer, but we can delve further into the problem’s inner workings. To do so, it helps to adopt a new way of looking at numbers: modular arithmetic.
-
