Chinese remainder theorem

Chinese remainder theorem refers to a result about congruences in number theory and its generalizations in abstract algebra.

Theorem statement

The original form of the theorem, contained in a third-century AD book Sun Zi suanjing(孙子算经 The Mathematical Classic by Sun Zi) by Chinese mathematician Sun Tzu and later republished in a 1247 book by Qin Jiushao, Shu shu jiu zhang(数书九章 Mathematical Treatise in Nine Sections) 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

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align}

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

Hence Failed to parse (Missing texvc executable; please see math/README to configure.): x\equiv y \pmod{n_i}

for all Failed to parse (Missing texvc executable; please see math/README to configure.): 1\leq i \leq k

, if and only if Failed to parse (Missing texvc executable; please see math/README to configure.): x \equiv y \pmod{N} .

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

Failed to parse (Missing texvc executable; please see math/README to configure.): a_i \equiv a_j \pmod{\gcd(n_i,n_j)} \qquad \mbox{for all }i\mbox{ and }j . \,\!

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

Versions of the Chinese remainder theorem were also known to Brahmagupta, and appear in Fibonacci's Liber Abaci (1202).

A constructive algorithm to find the solution

This algorithm only treats the situations where the Failed to parse (Missing texvc executable; please see math/README to configure.): 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:

Failed to parse (Missing texvc executable; please see math/README to configure.): x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \ldots, k.

Again, to begin, the product Failed to parse (Missing texvc executable; please see math/README to configure.): N=n_1n_2\ldots n_k

is defined. Then a solution x can be found as follows. 

For each i the integers Failed to parse (Missing texvc executable; please see math/README to configure.): n_i

and Failed to parse (Missing texvc executable; please see math/README to configure.): N/n_i
are coprime. Using the extended Euclidean algorithm we can therefore find integers Failed to parse (Missing texvc executable; please see math/README to configure.): r_i
and Failed to parse (Missing texvc executable; please see math/README to configure.): s_i
such that Failed to parse (Missing texvc executable; please see math/README to configure.): r_in_i + s_iN/n_i = 1

. Then, choosing the label Failed to parse (Missing texvc executable; please see math/README to configure.): e_i=s_iN/n_i , the above expression becomes:

Failed to parse (Missing texvc executable; please see math/README to configure.): r_i n_i + e_i = 1 \,\!

Consider Failed to parse (Missing texvc executable; please see math/README to configure.): e_i . The above equation guarantees that its remainder, when divided by Failed to parse (Missing texvc executable; please see math/README to configure.): n_i , must be 1. On the other hand, since it is formed as Failed to parse (Missing texvc executable; please see math/README to configure.): s_iN/n_i , the presence of Failed to parse (Missing texvc executable; please see math/README to configure.): N

guarantees that it's evenly divisible by any Failed to parse (Missing texvc executable; please see math/README to configure.): n_j
so long as Failed to parse (Missing texvc executable; please see math/README to configure.): j\ne i

.

Failed to parse (Missing texvc executable; please see math/README to configure.): e_i \equiv 1 \pmod{n_i} \quad \mathrm{and} \quad e_i \equiv 0 \pmod{n_j} \quad \mathrm{for} ~ i \ne j

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

Failed to parse (Missing texvc executable; please see math/README to configure.): x = \sum_{i=1}^k a_i e_i.\!

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

Failed to parse (Missing texvc executable; please see math/README to configure.): x \equiv 2 \pmod{3}, \,\!

Failed to parse (Missing texvc executable; please see math/README to configure.): x \equiv 3 \pmod{4}, \,\!

Failed to parse (Missing texvc executable; please see math/README to configure.): x \equiv 1 \pmod{5}. \,\!

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 + 1 × (−24) = 191. All other solutions are congruent to 191 modulo 60, (3 × 4 × 5 = 60) which means that they are all congruent to 11 modulo 60.

NOTE: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of Failed to parse (Missing texvc executable; please see math/README to configure.): e_1 , Failed to parse (Missing texvc executable; please see math/README to configure.): e_2 , and Failed to parse (Missing texvc executable; please see math/README to configure.): e_3 . These sets however will produce the same solution i.e. 11 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

Failed to parse (Missing texvc executable; please see math/README to configure.): f : R/uR \rightarrow R/u_1R \times \cdots \times R/u_k R

such that

Failed to parse (Missing texvc executable; please see math/README to configure.): f(x +uR) = (x + u_1R, \ldots , x +u_kR) \quad\mbox{ for every } x\in R.

This isomorphism is unique; 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

Failed to parse (Missing texvc executable; please see math/README to configure.): r u_i + s u/u_i = 1. \,\!

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

Failed to parse (Missing texvc executable; please see math/README to configure.): g : R/u_1R \times \cdots \times R/u_kR \rightarrow R/uR

such that

Failed to parse (Missing texvc executable; please see math/README to configure.): g(a_1+u_1R,\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

Failed to parse (Missing texvc executable; please see math/README to configure.): x \equiv a_i \pmod{u_i} \quad\mathrm{for}\; i = 1, \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 commutative rings and ideals. If R is a commutative 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

Failed to parse (Missing texvc executable; please see math/README to configure.): f : R/I \rightarrow R/I_1 \times \cdots \times R/I_k

such that

Failed to parse (Missing texvc executable; please see math/README to configure.): f(x + I) = (x +I_1, \ldots , x+I_k) \quad\mbox{ for all } x\in R.

Applications

In the RSA algorithm calculations are made modulo Failed to parse (Missing texvc executable; please see math/README to configure.): n , where Failed to parse (Missing texvc executable; please see math/README to configure.): n

is a product of two large prime numbers Failed to parse (Missing texvc executable; please see math/README to configure.): p
and Failed to parse (Missing texvc executable; please see math/README to configure.): q

. 1024-, 2048- or 4096-bit integers Failed to parse (Missing texvc executable; please see math/README to configure.): n

are commonly used, making calculations in Failed to parse (Missing texvc executable; please see math/README to configure.): \Bbb{Z}/n\Bbb{Z}
very time-consuming. By the Chinese Remainder Theorem, however, these calculations can be done in the isomorphic ring Failed to parse (Missing texvc executable; please see math/README to configure.): \Bbb{Z}/p\Bbb{Z} \oplus \Bbb{Z}/q\Bbb{Z}
instead. Since Failed to parse (Missing texvc executable; please see math/README to configure.): p
and Failed to parse (Missing texvc executable; please see math/README to configure.): q
are normally of about the same size, that is about Failed to parse (Missing texvc executable; please see math/README to configure.): \sqrt{n}

, calculations in the latter representation are much faster. Note that RSA algorithm implementations using this isomorphism are more susceptible to fault injection attacks.

The Chinese Remainder Theorem may also be used to construct an elegant Gödel numbering for sequences, which is needed to prove Gödel's incompleteness theorems.

Non-commutative case

The Chinese remainder theorem does not hold in the non-commutative case. Consider the ring Failed to parse (Missing texvc executable; please see math/README to configure.): R

of non-commutative real polynomials in Failed to parse (Missing texvc executable; please see math/README to configure.): x
and Failed to parse (Missing texvc executable; please see math/README to configure.): y

. Let Failed to parse (Missing texvc executable; please see math/README to configure.): I

be the principal two-sided ideal generated by Failed to parse (Missing texvc executable; please see math/README to configure.): x
and Failed to parse (Missing texvc executable; please see math/README to configure.): J
the principal two-sided ideal generated by Failed to parse (Missing texvc executable; please see math/README to configure.): xy+1.
Then Failed to parse (Missing texvc executable; please see math/README to configure.): I+J=R
but Failed to parse (Missing texvc executable; please see math/README to configure.): I\cap J \neq IJ.

Proof:

Observe that Failed to parse (Missing texvc executable; please see math/README to configure.): I

is formed by all polynomials with an Failed to parse (Missing texvc executable; please see math/README to configure.): x
in every term and that every polynomial in Failed to parse (Missing texvc executable; please see math/README to configure.): J
vanishes under the substitution Failed to parse (Missing texvc executable; please see math/README to configure.): y=-1/x

. Consider the polynomial Failed to parse (Missing texvc executable; please see math/README to configure.): p=(xy+1)x . Clearly Failed to parse (Missing texvc executable; please see math/README to configure.): p\in I\cap J . Define a term in Failed to parse (Missing texvc executable; please see math/README to configure.): R

as an element of the multiplicative monoid of Failed to parse (Missing texvc executable; please see math/README to configure.): R
generated by Failed to parse (Missing texvc executable; please see math/README to configure.): x
and Failed to parse (Missing texvc executable; please see math/README to configure.): y

. Define the degree of a term as the usual degree of the term after the substitution Failed to parse (Missing texvc executable; please see math/README to configure.): y=x . On the other hand, suppose Failed to parse (Missing texvc executable; please see math/README to configure.): q\in J . Observe that a term in Failed to parse (Missing texvc executable; please see math/README to configure.): q

of maximum degree depends on Failed to parse (Missing texvc executable; please see math/README to configure.): y
otherwise Failed to parse (Missing texvc executable; please see math/README to configure.): q
under the  substitution Failed to parse (Missing texvc executable; please see math/README to configure.): y=-1/x
can not vanish. The same happens then for an element Failed to parse (Missing texvc executable; please see math/README to configure.): q\in IJ

. Observe that the last Failed to parse (Missing texvc executable; please see math/README to configure.): y , from left to right, in a term of maximum degree in an element of Failed to parse (Missing texvc executable; please see math/README to configure.): IJ

is preceded by more than one Failed to parse (Missing texvc executable; please see math/README to configure.): x

. (We are counting here all the preceding Failed to parse (Missing texvc executable; please see math/README to configure.): x s. e.g. in Failed to parse (Missing texvc executable; please see math/README to configure.): x^2yxyx^5

the last Failed to parse (Missing texvc executable; please see math/README to configure.): y
is preceded by  Failed to parse (Missing texvc executable; please see math/README to configure.): 3
Failed to parse (Missing texvc executable; please see math/README to configure.): x

s.) This proves that Failed to parse (Missing texvc executable; please see math/README to configure.): (xy+1)x\notin IJ

since that last  Failed to parse (Missing texvc executable; please see math/README to configure.): y
in a term of maximum degree ( Failed to parse (Missing texvc executable; please see math/README to configure.): xyx
) is preceded by only one Failed to parse (Missing texvc executable; please see math/README to configure.): x

. Hence Failed to parse (Missing texvc executable; please see math/README to configure.): I\cap J\neq IJ .

On the other hand, it is true in general that Failed to parse (Missing texvc executable; please see math/README to configure.): I+J = R

implies Failed to parse (Missing texvc executable; please see math/README to configure.): I \cap J = IJ + JI

. To see this, note that Failed to parse (Missing texvc executable; please see math/README to configure.): I \cap J = (I \cap J) (I+J) \subset IJ + JI , while the opposite inclusion is obvious. Also, we have in general that, provided Failed to parse (Missing texvc executable; please see math/README to configure.): I_1, \ldots, I_m

are

pairwise coprime two-sided ideals in Failed to parse (Missing texvc executable; please see math/README to configure.): R , the natural map

Failed to parse (Missing texvc executable; please see math/README to configure.): R / (I_1 \cap I_2 \cap \ldots \cap I_m) \rightarrow R/I_1 \oplus R/I_2 \oplus \cdots \oplus R/I_m

is an isomorphism. Note that Failed to parse (Missing texvc executable; please see math/README to configure.): I_1 \cap I_2 \cap \ldots \cap I_m

can be replaced by a sum over all orderings of

Failed to parse (Missing texvc executable; please see math/README to configure.): I_1, \ldots, I_m

of their product (or just a sum over enough orderings, using inductively that Failed to parse (Missing texvc executable; please see math/README to configure.): I \cap J = IJ + JI

for coprime ideals Failed to parse (Missing texvc executable; please see math/README to configure.): I, J ).

See also

• Covering system
• Residue number system

External links

• Chinese remainder theorem at cut-the-knot
• "Chinese Remainder Theorem" by Ed Pegg, Jr., The Wolfram Demonstrations Project, 2007.

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 0-262-03293-7. Section 31.5: The Chinese remainder theorem, pp.873–876.
• Sigler, Laurence E. (trans.) (2002). Fibonacci's Liber Abaci. Springer-Verlag, 402–403. ISBN 0-387-95419-8. ar:مبرهنة الباقي الصيني

cs:Čínská věta o zbytcích de:Chinesischer Restsatz es:Teorema chino del resto fr:Théorème des restes chinois zh-classical:韓信點兵 id:Teorema sisa Tiongkok it:Teorema cinese del resto he:משפט השאריות הסיני hu:Kínai maradéktétel mn:Үлдэгдлийн тухай Хятадын теорем nl:Chinese reststelling ja:中国の剰余定理 pl:Chińskie twierdzenie o resztach pt:Teorema chinês do resto ru:Китайская теорема об остатках sv:Kinesiska restsatsen vi:Định lý số dư Trung Quốc ur:چینی تقسیم باقی مسلئہ اثباتی