Several related results in number theory and abstract algebra are known under the name Chinese remainder theorem. Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ...

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). (2nd century - 3rd century - 4th century - other centuries) Events The Sassanid dynasty of Persia launches a war to reconquer lost lands in the Roman east. ... Sun Tzu or Sun Zi was a Chinese mathematician of the third century. ... Events Shams ad-Din disappears resulting in Jalal Uddin Rumi writing 30,000 verses of poetry about his disappearance. ... Qin Jiushao (秦九韶) (1202 – 1261), also known as Chin Chiu-Shao, was a Chinese mathematician. ... Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

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 The integers are commonly denoted by the above symbol. ... In mathematics, especially number theory, a set of integers is said to be pairwise coprime (or pairwise relatively prime) if every pair of integers a and b in the set are coprime (that is, have no common divisors apart from 1). ...

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:

All solutions x are then congruent modulo the least common multiple of the n_i. In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ...

Versions of the Chinese remainder theorem were also known to Brahmagupta, and appear in Fibonacci's Liber Abaci (1202). Brahmagupta (ब्रह्मगुप्त) (598-668) was an Indian mathematician and astronomer. ... Leonardo of Pizza (1170s or 1180s – 1250), also known as Leonardo Pisano, Leonardo Bonacci, Leonardo Fibonacci, or, most commonly, simply Fibonacci, was an Italian mathematician, considered by some the most talented mathematician of the Middle Ages. ... Liber Abaci (1202) is an historic book on arithmetic by Leonardo of Pisa, known later by his nickname Fibonacci. ...

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. In modular arithmetic, the method of successive substitution is a method of solving problems of simultaneous congruences by using the definition of the congruence equation. ...

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

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: The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of a and b: it also finds the integers x and y in Bezouts identity The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is...

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.

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₁ = 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, which means that they are all congruent to 11 modulo 60. The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of a and b: it also finds the integers x and y in Bezouts identity The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is...

NOTE: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of e₁, e₂, and e₃. These sets however will produce the same solution i.e. 11 modulo 60. The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of a and b: it also finds the integers x and y in Bezouts identity The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is...

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 In abstract algebra, a principal ideal domain (PID) is an integral domain in which every ideal is principal (that is, generated by a single element). ... In mathematics, especially number theory, a set of integers is said to be pairwise coprime (or pairwise relatively prime) if every pair of integers a and b in the set are coprime (that is, have no common divisors apart from 1). ... In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ... In abstract algebra, it is possible to combine several rings into one large product ring. ... In abstract algebra, a ring homomorphism is a function between two rings which respects the operations of addition and multiplication. ...

such that

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 The integers are commonly denoted by the above symbol. ... In mathematics, a surjective function (or onto function or surjection) is a function with the property that all possible output values of the function are generated when the input ranges over all the values in the domain. ...

can be solved for x, and the injectivity of the map f shows that all the solutions x are congruent modulo u. In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...

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 In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ... Coprime - Wikipedia /**/ @import /skins-1. ... In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ... In abstract algebra, it is possible to combine several rings into one large product ring. ... In abstract algebra, a ring homomorphism is a function between two rings which respects the operations of addition and multiplication. ...

such that

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 to the ring . 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. This article is about an algorithm for public-key encryption. ... This article is about the unit of information. ...

See also

• Covering system
• Residue number system

In mathematics, a covering system is a collection of finitely many residue classes whose union covers all integers. ... A residue number system (RNS) represents a large integer using a set of smaller integers, so that computation may be performed more efficiently. ...

External links

• Chinese remainder theorem at cut-the-knot

cut-the-knot is an educational website maintained by Alexander Bogomolny and devoted to popular exposition of a great variety of topics in mathematics. ...

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.