# Chinese remainder theorem

The **Chinese remainder theorem** is a result about congruences in number theory and its generalizations in abstract algebra. It was first published in the 3rd to 5th centuries by the Chinese mathematician Sun Tzu.

In its basic form, the Chinese remainder theorem will determine a number *n* that when divided by some given divisors leaves given remainders. For example, what is the lowest number *n* that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2?

## Theorem statement

The original form of the theorem, contained in the 5th-century book *Sunzi's Mathematical Classic* (孫子算經{{#invoke:Category handler|main}}) by the Chinese mathematician Sun Tzu and later generalized with a complete solution called *Dayanshu* (大衍術{{#invoke:Category handler|main}}) in Qin Jiushao's 1247 *Mathematical Treatise in Nine Sections* (數書九章{{#invoke:Category handler|main}}, *Shushu Jiuzhang*), is a statement about simultaneous congruences.

Suppose *n*_{1}, ..., *n _{k}* are positive integers that are pairwise coprime. Then, for any given sequence of integers

*a*

_{1}, ...,

*a*, there exists an integer Template:Mvar solving the following system of simultaneous congruences.

_{k}Furthermore, all solutions Template:Mvar of this system are congruent modulo the product, *N* = *n*_{1} ... *n _{k}*. Hence

Sometimes, the simultaneous congruences can be solved even if the *n _{i}* are not pairwise coprime. A solution Template:Mvar exists if and only if:

All solutions Template:Mvar are then congruent modulo the least common multiple of the *n _{i}*.

Sun Tzu's work contains neither a proof nor a full algorithm. What amounts to an algorithm for solving this problem was described by Aryabhata (6th century; see Template:Harvnb). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).

A modern restatement of the theorem in algebraic language is that for a positive integer with prime factorization

we have the isomorphism between a ring and the direct product of its prime power parts:

The theorem can also be restated in the language of combinatorics as the fact that the infinite arithmetic progressions of integers form a Helly family Template:Harv.

## Existence and uniqueness

The existence and uniqueness of the solution can easily be seen through a non-constructive argument:

There are *N* = *n*_{1} ... *n _{k}* different Template:Mvar-tuples of remainders. Let us call this set Template:Mvar. On the other hand

*N*= #{1, ...,

*N*}, and each element of {1, ...,

*N*} corresponds to an element of Template:Mvar. Can two numbers

*a*,

*b*∈ {1, ...,

*N*}, correspond to the same member of Template:Mvar? That is, can they have the same set of remainders when divided by

*n*

_{1}, ...,

*n*? If they did then

_{k}*a*−

*b*would be divisible by each Template:Mvar. Since the Template:Mvar are relatively prime,

*a*−

*b*would be divisible by their product: Template:Mvar. This can't be, so this function {1, ...,

*N*} →

*R*is one-to-one. Since #{1, ...,

*N*} = #

*R*, it must be onto as well. Thus we have established the existence of a bijection.

Existence can be seen by an explicit construction of Template:Mvar. Let [*a*^{−1}]_{b} denote the multiplicative inverse of *a* (mod *b*) given by the Extended Euclidean algorithm. It is defined exactly when Template:Mvar and Template:Mvar are coprime; the following construction explains why this condition is needed.

### Case of two equations (*k* = 2)

Consider the system:

Since gcd(*n*_{1}, *n*_{2}) = 1, Bézout's identity implies:

This is true because we are using the inverses provided by the Extended Euclidean algorithm; for any other inverses, this would not necessarily be true, but still be valid (mod *n*_{1}*n*_{2}).

Multiplying both sides by Template:Mvar, we get

If we take the congruence modulo *n*_{1} for the right-hand-side expression, it is readily seen that

But we know that *x* ≡ *a*_{1} (mod *n*_{1}), thus this suggests that the coefficient of the first term on the right-hand-side expression can be replaced by *a*_{1}. Similarly, we can show that the coefficient of the second term can be substituted by *a*_{2}. We can now define the value

and it is seen to satisfy both congruences, for example:

### General case

The same type of construction works in the general case of Template:Mvar congruence equations. Let *N* = *n*_{1} ... *n _{k}* be the product of every modulus then define

and this is seen to satisfy the system of congruences by a similar calculation as before.

## Finding the solution with basic algebra and modular arithmetic

For example, consider the problem of finding an integer Template:Mvar such that

### Brute-force approach

A brute-force approach converts these congruences into sets and writes the elements out to the product of 3×4×5 = 60 (the solutions modulo 60 for each congruence):

*x*∈ {2, 5, 8,**11**, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68,**71**, 74, ...}*x*∈ {3, 7,**11**, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67,**71**, 75, 79, ...}*x*∈ {1, 6,**11**, 16, 21, 26, 31, 36, 41, 46, 51, 56, 61, 66,**71**, 76, 81, 86, 91, 96, ...}

To find an x that satisfies all three congruences, intersect the three sets to get:

*x*∈ {11, 71, ...}

Which can be expressed as

### Algebraic approach

Another way to find a solution is with basic algebra, modular arithmetic, and stepwise substitution.

We start by translating these congruences into equations for some Template:Mvar, and Template:Mvar:

Start by substituting the Template:Mvar from the first equation into the second congruence:

meaning that *t* = 3 + 4*s* for some integer Template:Mvar. Substitute Template:Mvar into the first equation:

Substitute this Template:Mvar into the third congruence:

meaning that *s* = 0 + 5*u* for some integer Template:Mvar. Finally,

So, we have solutions {11, 71, 131, 191, ...}.

Notice that 60 = lcm(3,4,5). If the moduli are pairwise coprime (as they are in this example), the solutions will be congruent modulo their product.

## A constructive algorithm to find the solution

The following algorithm only applies if the *n _{i}* are pairwise coprime. (For simultaneous congruences when the moduli are not pairwise coprime, the method of successive substitution can often yield solutions.)

Suppose, as above, that a solution is required for the system of congruences:

Define: *N* = *n*_{1} ... *n _{k}*. For each Template:Mvar, the integers

*n*and {{ safesubst:#invoke:Unsubst||$B=

_{i}*N*/

*n*}} are coprime. Using the extended Euclidean algorithm we can find

_{i}*r*,

_{i}*s*∈

_{i}**Z**such that

*r*+ {{ safesubst:#invoke:Unsubst||$B=

_{i}n_{i}*s*/

_{i}N*n*}} = 1. Substitute

_{i}*e*for {{ safesubst:#invoke:Unsubst||$B=

_{i}*s*/

_{i}N*n*}}, to arrive at:

_{i}*r*+

_{i}n_{i}*e*= 1. So the remainder of

_{i}*e*divided by

_{i}*n*is 1. On the other hand,

_{i}*e*= {{ safesubst:#invoke:Unsubst||$B=

_{i}*s*/

_{i}N*n*}}, guarantees that

_{i}*n*divides

_{j}*e*for

_{i}*j*≠

*i*. To summarize:

Because of this, and the multiplication rules allowed in congruences, one solution to the system of simultaneous congruences is:

For example, consider the problem of finding an integer Template:Mvar such that

Using the extended Euclidean algorithm, for Template:Mvar modulo 3 and 20 [4 × 5], we find (−13) × 3 + 2 × 20 = 1; i.e., *e*_{1} = 40. For Template:Mvar modulo 4 and 15 [3 × 5], we get (−11) × 4 + 3 × 15 = 1, i.e. *e*_{2} = 45. Finally, for Template:Mvar modulo 5 and 12 [3 × 4], we get 5 × 5 + (−2) × 12 = 1, i.e. *e*_{3} = −24. A solution Template:Mvar is therefore 2 × 40 + 3 × 45 + 1 × (−24) = 191. All other solutions are congruent to 191 modulo 60, [3 × 4 × 5], which means they are all congruent to 11 modulo 60.

Note: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of *e*_{1} = −20, *e*_{2} = −15, and *e*_{3} = −24. These sets however will produce the same solution; i.e., (−20)2 + (−15)3 + (−24)1 = −109 ≡ 11 (mod 60).

## Statement for principal ideal domains

**Chinese Remainder Theorem for Principal Ideal Domains.**Let Template:Mvar be principal ideal domain. If*u*_{1}, ...,*u*are pairwise coprime elements of Template:Mvar where_{k}*u*=*u*_{1}...*u*, then the quotient ring_{k}*R/uR*and the product ring*R/u*_{1}*R*× ... ×*R/u*are isomorphic via the following map:_{k}R

This statement is a straightforward generalization of the above theorem about integer congruences: **Z** is a principal ideal domain, the surjectivity of the map *f* shows that every system of congruences of the form

can be solved for Template:Mvar, and the injectivity of the map *f* shows that all the solutions Template:Mvar are congruent modulo Template:Mvar.

**Proof.** This map is well-defined and a homomorphism of rings. An inverse homomorphism can be constructed as follows, showing that it is in fact an isomorphism. For each Template:Mvar, the elements *u _{i}* and

*u/u*are coprime, and therefore there exist elements Template:Mvar and Template:Mvar in Template:Mvar with

_{i}Set *e _{i}* =

*su/u*. Then it is clear that

_{i}Thus the inverse of *f* is the map

## Statement for general rings

The general form of the Chinese remainder theorem, which implies all the statements given above, can be formulated for commutative rings and ideals.

**Chinese Remainder Theorem for Commutative Rings.**If Template:Mvar is a commutative ring and*I*_{1}, ...,*I*are ideals of_{k}*R*that are pairwise coprime (meaning*I*+_{i}*I*=_{j}*R*for all*i*≠*j*), then the product Template:Mvar of these ideals is equal to their intersection, and the quotient ring*R/I*is isomorphic to the product ring*R*/*I*_{1}× ... ×*R*/*I*via the isomorphism_{k}

Here is a version of the theorem where *R* is not required to be commutative:

**Chinese Remainder Theorem for Noncommutative Rings.**Let Template:Mvar be any ring with 1 (not necessarily commutative) and*I*_{1}, ...,*I*be pairwise coprime 2-sided ideals. Then the canonical Template:Mvar-module homomorphism_{k}*R*→*R*/*I*_{1}× ... ×*R*/*I*is onto, with kernel_{k}*I*_{1}∩ ... ∩*I*. Hence, (as Template:Mvar-modules)._{k}

## Applications

### Sequence Numbering

The Chinese remainder theorem can be used to construct an elegant Gödel numbering for sequences, which is needed to prove Gödel's incompleteness theorems.

### Fast Fourier Transform

The Good-Thomas fast Fourier transform algorithm exploits a re-indexing of the data based on the Chinese remainder theorem. The Prime-factor FFT algorithm contains an implementation.

### Encryption

The Chinese remainder theorem can also be used in secret sharing, which consists of distributing a set of shares among a group of people who, all together (but no one alone), can recover a certain secret from the given set of shares. Each of the shares is represented in a congruence, and the solution of the system of congruences using the Chinese remainder theorem is the secret to be recovered. Secret Sharing using the Chinese Remainder Theorem uses, along with the Chinese remainder theorem, special sequences of integers that guarantee the impossibility of recovering the secret from a set of shares with less than a certain cardinality.

### Hermite Interpolation

**The General Hermite Interpolation Problem.**Given Template:Mvar complex points ("interpolation nodes")*λ*_{1}, ...,*λ*and complex data {_{r}*a*: 1 ≤_{j,k}*j*≤*r*, 0 ≤*k*<*ν*}, find_{j}*P*(*x*) ∈**C**[*x*] such that:

**Solution.** Introducing the polynomials

the problem may be equivalently reformulated as a system of Template:Mvar simultaneous congruences:

By the Chinese remainder theorem in the principal ideal domain **C**[*x*], there is a unique polynomial *P*(*x*) such that:

A direct construction, in analogy with the above proof for the integer number case, can be performed as follows. Define the polynomials

The partial fraction decomposition of {{ safesubst:#invoke:Unsubst||$B=1/*Q*}} gives Template:Mvar polynomials *S _{j}* with degrees deg(

*S*) <

_{j}*ν*such that

_{j}so that

Then a solution of the simultaneous congruence system is given by the polynomial

and the minimal degree solution is this one reduced modulo Template:Mvar, that is the unique with degree less than Template:Mvar.

### Dedekind's Theorem

**Dedekind's Theorem on the Linear Independence of Characters.**Let Template:Mvar be a monoid and Template:Mvar an integral domain, viewed as a monoid by considering the multiplication on Template:Mvar. Then any finite family (*f*)_{i}_{i∈I}of distinct monoid homomorphisms*f*:_{i}*M*→*k*is linearly independent. In other words every family (*α*)_{i}_{i∈I}of elements*α*∈_{i}*k*satisfying- must be equal to the family (0)
_{i∈I}.

**Proof.** First assume that Template:Mvar is a field, otherwise, replace the integral domain Template:Mvar by its quotient field, and nothing will change. We can linearly extend the monoid homomorphisms *f _{i}* :

*M*→

*k*to Template:Mvar-algebra homomorphisms

*F*:

_{i}*k*[

*M*] →

*k*, where

*k*[

*M*] is the monoid ring of Template:Mvar over Template:Mvar. Then, by linearity, the condition

yields

Next, for *i*, *j* ∈ *I*; *i* ≠ *j* the two Template:Mvar-linear maps *F _{i}* :

*k*[

*M*] →

*k*and

*F*:

_{j}*k*[

*M*] →

*k*are not proportional to each other. Otherwise

*f*and

_{i}*f*would also be proportional, and thus equal since as monoid homomorphisms they satisfy:

_{j}*f*(1) = 1 =

_{i}*f*(1), which contradicts the assumption that they are distinct.

_{j}Therefore the kernels Ker *F _{i}* and Ker

*F*are distinct. Since

_{j}*k*[

*M*]/Ker

*F*≅

_{i}*F*(

_{i}*k*[

*M*]) =

*k*is a field, Ker

*F*is a maximal ideal of

_{i}*k*[

*M*] for every

*i*∈

*I*. Because they are distinct and maximal the ideals Ker

*F*and Ker

_{i}*F*are coprime whenever

_{j}*i*≠

*j*. The Chinese Remainder Theorem (for general rings) yields an isomorphism:

where

Consequently, the map

is surjective. Under the isomorphisms *k*[*M*]/Ker *F _{i}* →

*F*(

_{i}*k*[

*M*]) =

*k*, the map Φ corresponds to:

Now,

yields

for every vector (*u _{i}*)

_{i∈I}in the image of the map Template:Mvar. Since Template:Mvar is surjective, this means that

for every vector

Consequently, (*α _{i}*)

_{i∈I}= (0)

_{i∈I}. QED.

## Non-commutative case: a caveat

Sometimes in the commutative case, the conclusion of the Chinese Remainder Theorem is stated as *R*/(*I*_{1} ... *I _{k}*) ≅

*R*/

*I*

_{1}× ... ×

*R*/

*I*. This version does not hold in the non-commutative case, since

_{k}*I*

_{1}∩ ... ∩

*I*≠

_{k}*I*

_{1}...

*I*, as can be seen from the following case:

_{k}**Proposition.**Let Template:Mvar be the ring of non-commutative real polynomials in Template:Mvar and Template:Mvar. Let Template:Mvar be the principal two-sided ideal generated by Template:Mvar and Template:Mvar the principal two-sided ideal generated by*xy*+ 1. Then*I*+*J*=*R*but*I*∩*J*≠*IJ*.

**Proof.** Observe that Template:Mvar is formed by all polynomials with an Template:Mvar in every term and that every polynomial in Template:Mvar vanishes under the substitution *y* = − {{ safesubst:#invoke:Unsubst||$B=1/*x*}}. Then clearly *p* = (*xy* + 1)*x* ∈ *I* ∩ *J*. Define a "term in Template:Mvar", as an element of the multiplicative monoid of Template:Mvar generated by Template:Mvar and Template:Mvar, and its degree as the usual degree of the term after the substitution *y* = *x*. On the other hand, suppose *q* ∈ *J*. Observe that a term in Template:Mvar of maximum degree depends on Template:Mvar otherwise Template:Mvar under the substitution *y* = − {{ safesubst:#invoke:Unsubst||$B=1/*x*}} can not vanish. The same happens then for an element *q* ∈ *IJ*. Note that the last Template:Mvar, from left to right, in a term of maximum degree in an element of Template:Mvar is preceded by more than one Template:Mvar. (We are counting here all the preceding Template:Mvars. E.g., in *x*^{2}*yxyx*^{5} the last Template:Mvar is preceded by three Template:Mvars.) This proves that *p* = (*xy* + 1)*x* ∉ *IJ* since the last Template:Mvar in the term of maximum degree in Template:Mvar (Template:Mvar) is preceded by only one Template:Mvar. Hence *I* ∩ *J* ≠ *IJ*.

However, it is true in general that *I* + *J* = *R* implies *I* ∩ *J* = *IJ* + *JI*. To see this, note that *I* ∩ *J* = (*I* ∩ *J*)(*I* + *J*) ⊂ *IJ* + *JI*, while the opposite inclusion is obvious. Also, we have in general that, provided *I*_{1}, ..., *I _{m}* are pairwise coprime two-sided ideals in Template:Mvar, the natural map

is an isomorphism. Note that *I*_{1} ∩ ... ∩ *I _{m}* can be replaced by a sum over all orderings of

*I*

_{1}, ...,

*I*of their product (or just a sum over enough orderings, using inductively that

_{m}*I*∩

*J*=

*IJ*+

*JI*for coprime ideals

*I*,

*J*⊂

*R*).

## See also

- Covering system
- Hasse principle
- Residue number system
- Secret sharing using the Chinese remainder theorem

## Notes

## References

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}. See Section 31.5: The Chinese remainder theorem, pp. 873–876.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}. See in particular Section 2.5, "Helly Property", pp. 393–394.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}. See Section 4.3.2 (pp. 286–291), exercise 4.6.2–3 (page 456).

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

## External links

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}