Chinese remainder theorem
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000: 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.




Chris K. Caldwell © 1999-2017 (all rights reserved)