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 <t5k.org> © Reginald McLean.