The original form of the theorem, contained in a book by the Chinese mathematician Ch'in ChiuShao[?] 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
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
For example, consider the problem of finding an integer x such that
Note that some systems of the form (1) can be solved even if the numbers n_{i} 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})) for all i and j. All solutions x are congruent modulo the least common multiple of the n_{i}.
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, und 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
f : R/uR > R/u_{1}R x ... x R/u_{k}R x mod uR > ( (x mod u_{1}R), ..., (x mod u_{k}R) )
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 r u_{i} + s u/u_{i} = 1. Set e_{i} = s u/u_{i}. Then the map
g : R/u_{1}R x ... x R/u_{k}R > R/uR ( (a_{1} mod u_{1}R), ..., (a_{k} mod u_{k}R) ) > ∑_{i=1..k} a_{i} e_{i} mod uR
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
f : R/I > R/I_{1} x ... x R/I_{k} x mod I > ( (x mod I_{1}), ..., (x mod I_{k}) )
Search Encyclopedia

Featured Article
