This site will be down for maintenance beginning noon CDT (5pm UTC) Wed April 14
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 n_{1}, n_{2}, ..., n_{k} are pairwise relatively prime integers. If a_{1}, a_{2}, ..., a_{k} are any integers, then
- There exists an integer a such a ≡ a_{i} (mod n_{i}) for each i = 1, 2, ..., k, and
- If b ≡ a_{i} (mod n_{i}) for each i = 1, 2, ..., k, then b ≡ a (mod n_{1}n_{2}...n_{k}).
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.
Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.