Several related results in number theory and abstract algebra are known under the name Chinese remainder theorem.

Theorem statement

---

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₁, n₂, …, n_k are integers which are pairwise coprime. Then, for any given integers a₁,a₂, …, a_k, there exists an integer x solving the system of simultaneous congruences

$x\; \backslash equiv\; a\_1\; \backslash pmod\{n\_1\}\; \backslash ,\backslash !$

$x\; \backslash equiv\; a\_2\; \backslash pmod\{n\_2\}\; \backslash ,\backslash !$

$\backslash vdots\; \backslash ,\backslash !$

$x\; \backslash equiv\; a\_k\; \backslash pmod\{n\_k\}\; \backslash ,\backslash !$

Furthermore, all solutions x to this system are congruent modulo the product N = n₁n₂…n_k.

Sometimes, the simultaneous congruences can be solved even if the n_is are not pairwise coprime. A solution x exists if and only if:

$a\_i\; \backslash equiv\; a\_j\; \backslash pmod\{\backslash gcd(n\_i,n\_j)\}\; \backslash qquad\; \backslash mbox\{for\; all\; \}i\backslash mbox\{\; and\; \}j\; .\; \backslash ,\backslash !$

All solutions x are then congruent modulo the least common multiple of the n_i.

A constructive algorithm to find the solution

---

This algorithm only treats the situations where the n_i's are coprime. The method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.

Suppose, as above, that a solution is needed to the system of congruences:

$x\; \backslash equiv\; a\_i\; \backslash pmod\{n\_i\}\; \backslash quad\backslash mathrm\{for\}\backslash ;\; i\; =\; 1,\; \backslash ldots,\; k.$

Again, to begin, the product N = n₁n₂…n_k is defined. Then a solution x can be found as follows.

For each i the integers n_i and N/n_i are coprime. Using the extended Euclidean algorithm we can therefore find integers r_i and s_i such that r_i n_i + s_i N/n_i = 1. Then, choosing the label e_i = s_i N/n_i, the above expression becomes:

$r\_i\; n\_i\; +\; e\_i\; =\; 1\; \backslash ,\backslash !$

Consider e_i. The above equation guarantees that its remainder, when divided by n_i, must be 1. On the other hand, since it is formed as s_i N/n_i, the presence of N guarantees that it's evenly divisible by any n_j so long as j ≠ i.

$e\_i\; \backslash equiv\; 1\; \backslash pmod\{n\_i\}\; \backslash quad\; \backslash mathrm\{and\}\; \backslash quad\; e\_i\; \backslash equiv\; 0\; \backslash pmod\{n\_j\}\; \backslash quad\; \backslash mathrm\{for\}\; ~\; i\; \backslash ne\; j$

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

$x\; =\; \backslash sum\_\{i=1\}^k\; a\_i\; e\_i.\backslash$

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

$x\; \backslash equiv\; 2\; \backslash pmod\{3\},\; \backslash ,\backslash !$

$x\; \backslash equiv\; 3\; \backslash pmod\{4\},\; \backslash ,\backslash !$

$x\; \backslash equiv\; 2\; \backslash pmod\{5\}.\; \backslash ,\backslash !$

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.

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, and u denotes the product u₁...u_k, then the quotient ring R/uR and the product ring R/u₁R × ⋯ × R/u_kR are isomorphic via the isomorphism

$f\; :\; R/uR\; \backslash rightarrow\; R/u\_1R\; \backslash times\; \backslash cdots\; \backslash times$

R/u_k R

such that

$f(x\; +uR)\; =\; (x\; +\; u\_1R,\; \backslash ldots\; ,\; x\; +u\_kR)\; \backslash quad\backslash mbox\{\; for\; every\; \}\; x\backslash in\; 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.\; \backslash ,\backslash !$

Set e_i = s u/u_i. Then the inverse of f is the map

$g\; :\; R/u\_1R\; \backslash times\; \backslash cdots\; \backslash times\; R/u\_kR$

\rightarrow R/uR

such that

$g(a\_1+u\_1R,\backslash ldots\; ,a\_k+u\_kR)=$

\left( \sum_{i=1}^k a_i e_i \right) + uR \quad\mbox{ for all }a_1,\ldots,a_k\in R.

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

$x\; \backslash equiv\; a\_i\; \backslash pmod\{u\_i\}\; \backslash quad\backslash mathrm\{for\}\backslash ;\; i\; =\; 1,\; \backslash ldots,\; k$

can be solved for x, and the injectivity of the map f shows that all the solutions x are congruent modulo u.

Statement for general rings

---

The general form of the Chinese remainder theorem, which implies all the statements given above, can be formulated for rings and (two-sided) ideals. If R is a ring and I₁, ..., I_k are two-sided 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 quotient 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\; \backslash rightarrow\; R/I\_1\; \backslash times\; \backslash cdots\; \backslash times\; R/I\_k$

such that

$f(x\; +\; I)\; =\; (x\; +I\_1,\; \backslash ldots\; ,\; x+I\_k)\; \backslash quad\backslash mbox\{\; for\; all\; \}\; x\backslash in\; R.$

Applications

---

In the RSA algorithm calculations are made modulo $n$, where $n$ is a product of two primes $p$ and $q$. Common sizes for $n$ are 1024, 2048 or 4096 bits, making calculations very time-consuming. Using Chinese remaindering these calculations can be transported from the ring $\backslash Bbb\{Z\}\_n$ to the ring $\backslash Bbb\{Z\}\_p\; \backslash times\; \backslash Bbb\{Z\}\_q$. The sum of the bit sizes of $p$ and $q$ is the bit size of $n$, making $p$ and $q$ considerably smaller than $n$. This greatly simplifies calculations.

Another potential application of Chinese remainder theorem is for counting soldiers in an army. Via Chinese remainder theorem, the general has the soldiers quickly line up in groups of 2, 3, 5, 7, 11, and so on and counts the remaining soldiers that can't make complete groups. After enough of these tests are made, the general can quickly calculate how many soldiers he has exactly; thus he has done a 3 hour headcount in all of 2 minutes. This fact, that a large number can be represented by a small number of relatively small remainders, is also the core idea of residue number systems.

See also

---

• Covering system
• Residue number system

External links

---

• Chinese remainder theorem at cut-the-knot

References

---

• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.3.2 (pp.286–291), exercise 4.6.2–3 (page 456).
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 31.5: The Chinese remainder theorem, pp.873–876.

Modular arithmetic | Commutative algebra | Mathematical theorems

Chinesischer Restsatz | Teorema chino del resto | Théorème des restes chinois | Teorema sisa Cina | Teorema cinese del resto | משפט השאריות הסיני | Chinese reststelling | 中国の剰余定理 | Chińskie twierdzenie o resztach | Китайская теорема об остатках | Kinesiska restsatsen | 中国剩余定理