 Chinese remainder theorem

The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.
In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers. For example what is the single lowest number if repeatedly divided by 3 gives a remainder of 2; when divided by 5 gives a remainder of 3; and when divided by 7 gives a remainder of 2?
Contents
Theorem statement
The original form of the theorem, contained in a thirdcentury 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 sequence of integers a_{1},a_{2}, …, a_{k}, there exists an integer x solving the following system of simultaneous congruences.
Furthermore, all solutions x of this system are congruent modulo to 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}.
Sun Zi'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 Kak 1986). 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 the algebraic language is that for a positive integer n with prime factorization we have the isomorphism between a ring and the direct product of its prime power parts:
Existence
Existence can be seen by an explicit construction of x. We will use the notation [a ^{− 1}]_{b} to denote the inverse of a(mod b), it is defined exactly when a and b are coprime  the following construction explains why the coprimality condition is needed.
Case of two equations
Given the system (corresponding to k = 2)
We define the value
and it is seen to satisfy both congruences by reducing. For example
General case
The same type of construction works in the general case of k congruence equations. Let be the product of every modulus then define
and this is seen to satisfy the system of congruences by a similar calculation as before.
A constructive algorithm to find the solution
The following algorithm only applies if the n_{i}'s 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:
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 x modulo 3 and 20 [4×5], we find (−13) × 3 + 2 × 20 = 1, i.e. e_{1} = 40. For x modulo 4 and 15 [3×5], we get (−11) × 4 + 3 × 15 = 1, i.e. e_{2} = 45. Finally, for x modulo 5 and 12 [3×4], we get 5 × 5 + (−2) × 12 = 1, i.e. 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} = − 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 modulo 60.
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_{k}, then the quotient ring R/uR and the product ring R/u_{1}R× ... × R/u_{k}R are isomorphic via the isomorphism
such that
This map is welldefined and an isomorphism of rings; 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
Set e_{i} = s u/u_{i}. Then the inverse of 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.
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 for all i), 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
Here is a version of the theorem where R is not required to be commutative:
Let R be any ring with 1 (not necessarily commutative) and be pairwise coprime 2sided ideals. Then the canonical Rmodule homomorphism is onto, with kernel . Hence, (as Rmodules).
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 4096bit integers n are commonly used, making calculations in very timeconsuming. 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 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.
 The GoodThomas fast Fourier transform algorithm exploits a reindexing of the data based on the Chinese remainder theorem. See the Primefactor FFT algorithm article for details.
 Dedekind's theorem on the linear independence of characters states (in one of its most general forms) that if M is a monoid and k is an integral domain, then any finite family of distinct monoid homomorphisms (where the monoid structure on k is given by multiplication) is linearly independent, i. e. every family of elements satisfying must be equal to the family .
 Proof using the Chinese Remainder Theorem: First, assume that k is a field (otherwise, replace the integral domain k by its quotient field, and nothing will change). We can linearly extend the monoid homomorphisms to kalgebra homomorphisms , where is the monoid ring of M over k. Then, the condition yields by linearity. Now, we notice that if are two elements of the index set I, then the two klinear maps and are not proportional to each other (because if they were, then f_{i} and f_{j} would also be proportional to each other, and thus equal to each other since (since f_{i} and f_{j} are monoid homomorphisms), contradicting the assumption that they be distinct). Hence, their kernels KerF_{i} and KerF_{j} are distinct. Now, KerF_{i} is a maximal ideal of for every (since is a field), and the ideals KerF_{i} and KerF_{j} are coprime whenever (since they are distinct and maximal). The Chinese Remainder Theorem (for general rings) thus yields that the map
 given by
 for all
 is an isomorphism, where . Consequently, the map
 given by
 for all
 is surjective. Under the isomorphisms , this map Φ corresponds to the map
 given by
 for every .
 Now, yields for every vector in the image of the map ψ. Since ψ is surjective, this means that for every vector . Consequently, , qed.
Noncommutative case: a counterexample
The Chinese remainder theorem does not hold in the noncommutative case. Consider the ring R of noncommutative real polynomials in x and y. Let I be the principal twosided ideal generated by x and J the principal twosided ideal generated by xy + 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 = (xy + 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 IJ is preceded by more than one x. (We are counting here all the preceding xs. e.g. in x^{2}yxyx^{5} the last y is preceded by 3 xs.) This proves that since that last y in a term of maximum degree (xyx) 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 twosided 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).
See also
 Covering system
 Hasse principle
 Residue number system
 Secret sharing using the Chinese remainder theorem
References
 Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. AddisonWesley, 1997. ISBN 0201896842. 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 McGrawHill, 2001. ISBN 0262032937. Section 31.5: The Chinese remainder theorem, pp.873–876.
 Laurence E. Sigler (trans.) (2002). Fibonacci's Liber Abaci. SpringerVerlag. pp. 402–403. ISBN 0387954198.
 Kak, Subhash (1986), "Computational aspects of the Aryabhata algorithm", Indian Journal of History of Science 21 (1): 62–71, http://www.ece.lsu.edu/kak/AryabhataAlgorithm.pdf.
 Thomas W. Hungerford (1974). Algebra. SpringerVerlag. pp. 131–132. ISBN 0387905189.
 Cunsheng Ding, Dingyi Pei, and Arto Salomaa (1996). Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography. World Scientific Publishing. pp. 1–213. ISBN 9810228279.
External links
 "Chinese Remainder Theorem" by Ed Pegg, Jr., Wolfram Demonstrations Project, 2007.
 Weisstein, Eric W., "Chinese Remainder Theorem" from MathWorld.
 C# program and discussion at codeproject
 University of Hawaii System CRT by Lee Lady
 Full text of the Sunzi Suanjing (Chinese)  Chinese Text Project
Categories: Modular arithmetic
 Commutative algebra
 Theorems in number theory
 Chinese mathematics
Wikimedia Foundation. 2010.