The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.
Contents
Theorem statement
The original form of the theorem, contained in a thirdcentury AD book Sun Zi suanjing (孫子算經 The Mathematical Classic by Sun Zi) by Chinese mathematician Sun Tzu and later republished in a 1247 book by Qin Jiushao, the Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections) is a statement about simultaneous congruences (see modular arithmetic).
Suppose n_{1}, n_{2}, …, n_{k} are positive integers which are pairwise coprime. Then, for any given set of integers a_{1},a_{2}, …, a_{k}, there exists an integer x solving the system of simultaneous congruences
Furthermore, all solutions x to this system are congruent modulo the product N = n_{1}n_{2}…n_{k}.
Hence for all , if and only if .
Sometimes, the simultaneous congruences can be solved even if the n_{i}'s are not pairwise coprime. A solution x exists if and only if:
All solutions x are then congruent modulo the least common multiple of the n_{i}.
An alternative method for solving similar systems of equations was described by Aryabhata (6th century; see Kak 1986). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).
A constructive algorithm to find the solution
The following algorithm only applies if the n_{i}'s are pairwise coprime. (For simultaneous congruences when the moduli are not pairwise coprime, the method of successive substitution can often yield solutions.)
Full article ▸
