chapter  6
26 Pages

Chinese Remainder Theorem

Chinese graduate students tell a wonderful story of a Chinese general who used an unusual method to count his troops. He gathered them together on a large parade field, told them to form groups of 11, and asked the leftovers to gather in front of the reviewing stand. He counted the number of leftovers, and then told the troops to reassemble into groups of 12, again with the leftovers up front. After repeating this process with 13, 17, and 19, he did some quick mental calculations to determine the exact number of troops on the parade field.