A 1,500-year-old Chinese puzzle now speeds up giant computer calculations
An old Chinese manual poses a riddle: count some objects in threes and two are left over, in fives and three remain, in sevens and two remain. How many are there? The answer, 23, rests on a rule now used to split huge computations into many small, fast ones.
The riddle comes from Sunzi Suanjing, a Chinese text written sometime between the third and fifth centuries CE, which is why the result is also called Sunzi's theorem. Sunzi only posed that one example, without a general method or proof. Knowing the remainders after dividing by 3, 5 and 7 fixes the remainder after dividing by their product, 105, and 23 is the only positive answer below 105.
The general rule says that if the divisors share no common factor except 1, then the remainders from each one pin down a single number below their product. Uniqueness is easy to see. If two numbers leave the same remainders, their difference is a multiple of every divisor, and so of the product, which forces them to be equal if both are smaller than it. Existence can then be argued by counting, or built explicitly using the extended Euclidean algorithm.
Many minds chipped away at it. Aryabhata described a method for solving such problems in the sixth century, Brahmagupta knew special cases in the seventh, and Fibonacci included some in his Liber Abaci of 1202. Qin Jiushao gave a complete solution, called Da-yan-shu, in his Mathematical Treatise in Nine Sections in 1247. Carl Friedrich Gauss introduced the language of congruences in 1801 and illustrated the theorem with a calendar puzzle about matching solar and lunar cycles.
Its modern payoff is speed. Arithmetic on enormous numbers can be replaced by the same arithmetic done separately with several small divisors, and the pieces are stitched back together at the end. Under the name multi-modular computation, this trick is widely used for exact linear algebra over whole numbers and fractions.
Source: Chinese remainder theorem
