Chinese remainder theorem

Chinese remainder theorem

The Chinese remainder theorem is the name applied to a number of related results in abstract algebra and number theory.

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)

Furthermore, all solutions x to this system are congruent modulo the product n = n₁...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 (mod n_i) and e_i ≡ 0 (mod n_j) for j ≠ i.

The number x = ∑_i=1..k a_i e_i then solves the given system (1) of simultaneous congruences.

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

x ≡ 2 (mod 3)

x ≡ 3 (mod 4)

x ≡ 2 (mod 5)

Using the extended Euclidean algorithm for 3 and 4×5 = 20, we find (-13) × 3 + 2 × 20 = 1 (i.e. e₁ = 40). Using the Euclidean algorithm for 4 and 3×5 = 15, we get (-11) × 4 + 3 × 15 = 1 (hence e₂ = 45). Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (-2) × 12 = 1 (meaning e₃ = -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.

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.

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, und 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) )