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