# Chinese remainder theorem

### From Wikipedia, the free encyclopedia

The **Chinese remainder theorem** is a result about congruences in number theory and its generalizations in abstract algebra.

## Contents |

## [edit] 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, the *Shushu Jiuzhang* (數書九章 Mathematical Treatise in Nine Sections) is a statement about simultaneous congruences (see modular arithmetic).

Suppose *n*_{1}, *n*_{2}, …, *n*_{k} are positive integers which are pairwise coprime. Then, for any given integers *a*_{1},*a*_{2}, …, *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*_{2}…*n*_{k}.

Hence for all , if and only if .

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:

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 (7th century), and appear in Fibonacci's Liber Abaci (1202).

## [edit] 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:

Again, to begin, the product 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 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:

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 .

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

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 + 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 *e*_{1}, *e*_{2}, and *e*_{3}. These sets however will produce the same solution i.e. 11 modulo 60.

## [edit] 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 quotient ring

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

*R/u*

_{1}

*R*× ... ×

*R/u*are isomorphic via the isomorphism

_{k}Rsuch that

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

Set *e _{i}* =

*s u/u*. Then the inverse of

_{i}*f*is the map

such that

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

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

## [edit] 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*_{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 quotient 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

## [edit] Applications

- In the RSA algorithm calculations are made modulo
*n*, where*n*is a product of two large prime numbers*p*and*q*. 1024-, 2048- or 4096-bit integers*n*are commonly used, making calculations in very time-consuming. By the Chinese Remainder Theorem, however, these calculations can be done in the isomorphic ring instead. Since*p*and*q*are normally of about the same size, that is about , 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.

- The following example shows a connection with the classic polynomial interpolation theory. Let
*r*complex points ("interpolation nodes") be given, together with the complex data , for all and . The general Hermite interpolation problem asks for a polynomial taking the prescribed derivatives in each node :

- .
- Introducing the polynomials , the problem may be equivalently reformulated as a system of simultaneous congruences:
- .
- By the Chinese remainder theorem in the principal ideal domain , there is a unique such polynomial with degree . A direct construction, in analogy with the above proof for the integer number case, can be performed as follows. Define the polynomials and . The partial fraction decomposition of gives
*r*polynomials with degrees such that - ,
- 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 , that is the unique with degree less than
*n*.

- 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 noone 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.

## [edit] Non-commutative case

The Chinese remainder theorem does not hold in the non-commutative case. Consider the ring *R* of non-commutative real polynomials in *x* and *y*. Let *I* be the principal two-sided ideal generated by *x* and *J* the principal two-sided ideal generated by *x**y* + 1. Then *I* + *J* = *R* but

**Proof:**

Observe that *I* is formed by all polynomials with an *x* in every term and that every polynomial in *J* vanishes under the substitution *y* = − 1 / *x*. Consider the polynomial *p* = (*x**y* + 1)*x*. Clearly . Define a term in *R* as an element of the multiplicative monoid of *R* generated by *x* and *y*. Define the degree of a term as the usual degree of the term after the substitution *y* = *x*. On the other hand, suppose . Observe that a term in *q* of maximum degree depends on *y* otherwise *q* under the substitution *y* = − 1 / *x* can not vanish. The same happens then for an element . Observe that the last *y*, from left to right, in a term of maximum degree in an element of *I**J* is preceded by more than one *x*. (We are counting here all the preceding *x*s. e.g. in *x*^{2}*y**x**y**x*^{5} the last *y* is preceded by 3 *x*s.) This proves that since that last *y* in a term of maximum degree (*x**y**x*) is preceded by only one *x*. Hence .

On the other hand, it is true in general that *I* + *J* = *R* implies . To see this, note that , while the opposite inclusion is obvious. Also, we have in general that, provided are pairwise coprime two-sided ideals in *R*, the natural map

is an isomorphism. Note that can be replaced by a sum over all orderings of of their product (or just a sum over enough orderings, using inductively that for coprime ideals *I*,*J*).

## [edit] See also

- Covering system
- Residue number system
- Hasse principle
- Secret Sharing using the Chinese Remainder Theorem

## [edit] 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. pp. 402–403. ISBN 0-387-95419-8.