In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of these integers, under the condition that the divisors are pairwise coprime.
The earliest known statement of the theorem is by the Chinese mathematician Sun-tzu in the ''Sunzi Suanjing, Sun-tzu Suan-ching'' in the 3rd century CE.
The Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers.
The Chinese remainder theorem (expressed in terms of Modular arithmetic#Congruence, congruences) is true over every principal ideal domain. It has been generalized to any ring (mathematics), ring, with a formulation involving two-sided ideals.
The earliest known statement of the theorem, as a problem with specific numbers, appears in the 3rd-century book ''Sunzi Suanjing, Sun-tzu Suan-ching'' by the Chinese mathematician Sun-tzu:
Sun-tzu'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). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202). The result was later generalized with a complete solution called ''Da-yan-shu'' () in Qin Jiushao, Ch'in Chiu-shao's 1247 ''Mathematical Treatise in Nine Sections'' (, ''Shu-shu Chiu-chang'') which was translated into English in early 19th century by British missionary Alexander Wylie (missionary), Alexander Wylie.
The notion of congruences was first introduced and used by Carl Friedrich Gauss in his ''Disquisitiones Arithmeticae'' of 1801. Gauss illustrates the Chinese remainder theorem on a problem involving calendars, namely, "to find the years that have a certain period number with respect to the solar and lunar cycle and the Roman indiction." Gauss introduces a procedure for solving the problem that had already been used by Leonhard Euler but was in fact an ancient method that had appeared several times.
, ..., ''n''''k''
be integers greater than 1, which are often called ''modular arithmetic, moduli'' or ''Euclidean division, divisors''. Let us denote by ''N'' the product of the ''n''''i''
The Chinese remainder theorem asserts that if the ''n''''i''
are pairwise coprime, and if ''a''1
, ..., ''a''''k''
are integers such that 0 ≤ ''a''''i''
for every ''i'', then there is one and only one integer ''x'', such that 0 ≤ ''x'' < ''N'' and the remainder of the Euclidean division of ''x'' by ''n''''i''
for every ''i''.
This may be restated as follows in term of congruence relation, congruences:
If the ''n''''i''
are pairwise coprime, and if ''a''1
, ..., ''a''''k''
are any integers, then the system
has a solution, and any two solutions, say ''x''1
, are congruent modulo ''N'', that is, .
In abstract algebra, the theorem is often restated as: if the ''n''''i''
are pairwise coprime, the map
defines a ring isomorphism
between the ring (mathematics), ring of integers modulo n, integers modulo ''N'' and the direct product of the rings of integers modulo the ''n''''i''
. This means that for doing a sequence of arithmetic operations in
one may do the same computation independently in each
and then get the result by applying the isomorphism (from the right to the left). This may be much faster than the direct computation if ''N'' and the number of operations are large. This is widely used, under the name ''multi-modular computation'', for linear algebra over the integers or the rational numbers.
The theorem can also be restated in the language of combinatorics as the fact that the infinite arithmetic progressions of integers form a Helly family.
The existence and the uniqueness of the solution may be proven independently. However, the first proof of existence, given below, uses this uniqueness.
Suppose that and are both solutions to all the congruences. As and give the same remainder, when divided by , their difference is a multiple of each . As the are pairwise coprime, their product divides also , and thus and are congruent modulo . If and are supposed to be non negative and less than (as in the first statement of the theorem), then their difference may be a multiple of only if .
Existence (first proof)
maps congruence classes modulo to sequences of congruence classes modulo . The proof of uniqueness shows that this map is injective. As the domain of a function, domain and the codomain of this map have the same number of elements, the map is also surjective, which proves the existence of the solution.
This proof is very simple but does not provide any direct way for computing a solution. Moreover, it cannot be generalized to other situations where the following proof can.
Existence (constructive proof)
Existence may be established by an explicit construction of . This construction may be split into two steps, firstly by solving the problem in the case of two moduli, and the second one by extending this solution to the general case by mathematical induction, induction on the number of moduli.
Case of two moduli
We want to solve the system:
Bézout's identity asserts the existence of two integers
may be computed by the extended Euclidean algorithm.
A solution is given by
The second congruence is proved similarly, by exchanging the subscripts 1 and 2.
Consider a sequence of congruence equations:
are pairwise coprime. The two first equations have a solution
provided by the method of the previous section. The set of the solutions of these two first equations is the set of all solutions of the equation
As the other
are coprime with
this reduces solving the initial problem of equations to a similar problem with
equations. Iterating the process, one gets eventually the solutions of the initial problem.
Existence (direct construction)
For constructing a solution, it is not necessary to make an induction on the number of moduli. However, such a direct construction involves more computation with large numbers, which makes it less efficient and less used. Nevertheless, Lagrange interpolation is a special case of this construction, applied to polynomials instead of integers.
be the product of all moduli but one. As the
are pairwise coprime,
are coprime. Thus Bézout's identity applies, and there exist integers
A solution of the system of congruences is
In fact, as
is a multiple of
Consider a system of congruences:
are pairwise coprime, and let
In this section several methods are described for computing the unique solution for
, such that