Online Encyclopedia
Chinese remainder theorem
The Chinese remainder theorem is any of a number of related results in abstract algebra and number theory.
Contents 
Simultaneous congruences of integers
The original form of the theorem, contained in a book by the Chinese mathematician Qin Jiushao published in 1247, is a statement about simultaneous congruences (see modular arithmetic). Suppose n_{1}, ..., n_{k} are positive integers which are pairwise coprime (meaning gcd (n_{i}, n_{j}) = 1 whenever i ≠ j). Then, for any given integers a_{1}, ..., a_{k}, there exists an integer x solving the system of simultaneous congruences
Pseudocode "subtitle":
x_solves_it=true; for(i = 1; i <= k; i++) if(x != a[i] % n[i]) x_solves_it=false;
Furthermore, all solutions x to this system are congruent modulo the product n = n_{1}...n_{k}.
A solution x can be found as follows. For each i, the integers n_{i} and n/n_{i} are coprime, and using the extended Euclidean algorithm we can find integers r and s such that r n_{i} + s n/n_{i} = 1. If we set e_{i} = s n/n_{i}, then we have
e[i] == 1 % n[i] && e[i] == 0 % n[j];
for j ≠ i. The solution to the system of simultaneous congruences is therefore

x = ∑ a_{i}e_{i} i = 1..k
for(i=1; i<k; i++) x += a[i] * e[i];
For example, consider the problem of finding an integer x such that
x == 2 % 3 && x == 3 % 4 && x == 2 % 5
Using the extended Euclidean algorithm for 3 and 4×5 = 20, we find (13) × 3 + 2 × 20 = 1, i.e. e_{1} = 40 (e[1] == 40
). Using the Euclidean algorithm for 4 and 3×5 = 15, we get (11) × 4 + 3 × 15 = 1. Hence, e_{2} = 45 (e[2] == 45
). Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (2) × 12 = 1, meaning e_{3} = 24 (e[3] == 24
). A solution x is therefore 2 × 40 + 3 × 45 + 2 × (24) = 167. All other solutions are congruent to 167 modulo 60, which means that they are all congruent to 47 modulo 60.
Sometimes, the simultaneous congruences can be solved even if the n_{i}'s (n[i]'s) are not pairwise coprime. The precise criterion is as follows: a solution x exists if and only if a_{i} ≡ a_{j} (mod gcd(n_{i}, n_{j})) (a[i] == a[j] % gcd(n[i], n[j]
) for all i and j. All solutions x are congruent modulo the least common multiple of the n_{i} (n[i]
).
Using the method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.
Statement for principal ideal domains
For a principal ideal domain R the Chinese remainder theorem takes the following form: If u_{1}, ..., u_{k} are elements of R which are pairwise coprime, and u denotes the product u_{1}...u_{k}, then the ring R/uR and the product ring R/u_{1}R x ... x R/u_{k}R are isomorphic via the isomorphism
such that
The inverse isomorphism can be constructed as follows. For each i, the elements u_{i} and u/u_{i} are coprime, and therefore there exist elements r and s in R with
 ru_{i} + su / u_{i} = 1
Set e_{i} = s u/u_{i}. Then the inverse is the map
such that
Statement for general rings
One of the most general forms of the Chinese remainder theorem can be formulated for rings and (twosided) ideals. If R is a ring and I_{1}, ..., I_{k} are ideals of R which are pairwise coprime (meaning that I_{i} + I_{j} = R whenever i ≠ j), then the product I of these ideals is equal to their intersection, and the ring R/I is isomorphic to the product ring R/I_{1} x R/I_{2} x ... x R/I_{k} via the isomorphism
such that