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 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.
