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 aai (mod ni) for each i = 1, 2, ..., k, and
  • If bai (mod ni) for each i = 1, 2, ..., k, then ba (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.

Printed from the PrimePages <> © Reginald McLean.