# Chinese remainder theorem

The

**Chinese remainder theorem**is any of a number of related results in abstract algebra and number theory.

Table of contents |

2 Statement for principal ideal domains 3 Statement for general rings 4 External links |

## 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*_{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*) for_{i}*i*= 1...*k***(1)**

*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*are coprime, and using the extended Euclidean algorithm we can find integers

_{i}*r*and

*s*such that

*r n*+

_{i}*s*

*n*/

*n*= 1. If we set

_{i}*e*=

_{i}*s*

*n*/

*n*, then we have

_{i}*e*≡ 1 (_{i}**mod***n*) and_{i}*e*≡ 0 (_{i}**mod***n*) for_{j}*j*≠*i*.

*x*= ∑

_{i=1..k}

*a*then solves the given system

_{i}e_{i}**(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)

*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*)) for all

_{j}*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*_{1}, ..., *u _{k}* are elements of

*R*which are pairwise coprime, and

*u*denotes the product

*u*

_{1}...

*u*, then the ring

_{k}*R/uR*and the product ring

*R/u*

_{1}

*R*x ... x

*R/u*are isomorphic via the isomorphism

_{k}Rf :The inverse isomorphism can be constructed as follows. For eachR/uR-->R/u_{1}Rx ... xR/u_{k}RxmoduR|-> ( (xmodu_{1}R), ..., (xmodu_{k}R) )

*i*, the elements

*u*and

_{i}*u/u*are coprime, and therefore there exist elements

_{i}*r*and

*s*in

*R*with

*r u*+

_{i}*s u/u*= 1. Set

_{i}*e*=

_{i}*s u/u*. Then the map

_{i}g :R/u_{1}Rx ... xR/u_{k}R-->R/uR( (a_{1}modu_{1}R), ..., (amod_{k}u_{k}R) ) |-> ∑_{i=1..k}amod_{i}e_{i}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 ... xR/I_{k}xmodI|-> ( (xmodI_{1}), ..., (xmodI_{k}) )