Chinese remainder theorem

Simultaneous congruences of integers

The original form of the theorem, contained in a book by the Chinese mathematician Ch'in Chiu-Shao published in 1247, is a statement about simultaneous congruences (see modular arithmetic). Suppose n₁, ..., 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₁, ..., a_k, there exists an integer x solving the system of simultaneous congruences

x ≡ a_i (mod n_i)    for i = 1...k     (1)

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 (mod n_i)    and     e_i ≡ 0 (mod n_j)    for j ≠ i.

For example, consider the problem of finding an integer x such that

x ≡ 2 (mod 3)

x ≡ 3 (mod 4)

x ≡ 2 (mod 5)

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.

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₁, ..., u_k are elements of R which are pairwise coprime, and u denotes the product u₁...u_k, then the ring R/uR and the product ring R/u₁R x ... x R/u_kR are isomorphic via the isomorphism f : R/uR --> R/u₁R x ... x R/u_kR x mod uR |-> ( (x mod u₁R), ..., (x mod u_kR) )

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₁R x ... x R/u_kR --> R/uR ( (a₁ mod u₁R), ..., (a_k mod u_kR) ) |-> ∑_i=1..k a_i e_i mod uR

Statement for general rings

One of the most general forms of the Chinese remainder theorem can be formulated for rings and (two-sided) ideals. If R is a ring and I₁, ..., 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₁ x R/I₂ x ... x R/I_k via the isomorphism f : R/I --> R/I₁ x ... x R/I_k x mod I |-> ( (x mod I₁), ..., (x mod I_k) )

External Links

• Chinese remainder theorem

Referenced By