# Chinese remainder theorem

### From Exampleproblems

The **Chinese remainder theorem** (**CRT**) is the name for several related results in abstract algebra and number theory.

## Contents |

## Simultaneous congruences of integers

The original form of the theorem, contained in a third-century book by Chinese mathematician Sun Tzu and later republished in a 1247 book by Qin Jiushao, 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

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*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}for *j* ≠ *i*.

The solution to the system of simultaneous congruences is therefore

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

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.

Sometimes, the simultaneous congruences can be solved even if the *n _{i}*'s 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}Rsuch that

The inverse isomorphism can be constructed as follows. For each *i*, the elements *u _{i}* and

*u/u*are coprime, and therefore there exist elements

_{i}*r*and

*s*in

*R*with

*r**u*_{i}+*s**u*/*u*_{i}= 1.

Set *e _{i}* =

*s u/u*. Then the inverse is the map

_{i}such that

## 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

such that

## Applications of the Chinese remainder theorem

- Used in the RSA algorithm decryption.

## See also

## External links

fr:Théorème des restes chinois id:Teorema sisa Cina nl:Chinese reststelling ja:中国の剰余定理 pl:Chińskie twierdzenie o resztach sv:Kinesiska restsatsen zh:中国剩余定理