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₁, n₂, ..., n_k are pairwise relatively prime integers. If a₁, a₂, ..., 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₁n₂...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.