Chinese remainder theorem
The following theorem is traditionally known as the Chinese remainder theorem (though there is some evidence that it was known to the Greeks before the Chinese).
- Theorem. Let n1, n2, ..., nk are pairwise relatively prime integers. If a1, a2, ..., ak are any integers, then
- There exists an integer a such a ≡ ai (mod ni) for each i = 1, 2, ..., k, and
- If b ≡ ai (mod ni) for each i = 1, 2, ..., k, then b ≡ a (mod n1n2...nk).
It is said that the ancient Chinese used a variant of this theorem to count their soldiers by having them line up in rectangles of 7 by 7, 11 by 11, ... After counting only the remainders, they solved the associated system of equations for the smallest positive solution.