# Chinese remainder theorem

The

**Chinese remainder theorem** is the name applied to a number of related results in

abstract algebra and

number theory.

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*_{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

*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*_{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 (**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*_{1} = 40). Using the Euclidean algorithm for 4 and 3×5 = 15, we get (-11) × 4 + 3 × 15 = 1 (hence

*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). 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}.

Using the method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.

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

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*

### 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*_{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}) )