In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Chinese remainder theorem states that if one knows the remainders of the
Euclidean division of an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
''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
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s are
pairwise coprime (no two divisors share a common factor other than 1).
For example, if we know that the remainder of ''n'' divided by 3 is 2, the remainder of ''n'' divided by 5 is 3, and the remainder of ''n'' divided by 7 is 2, then without knowing the value of ''n'', we can determine that the remainder of ''n'' divided by 105 (the product of 3, 5, and 7) is 23. Importantly, this tells us that if ''n'' is a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
less than 105, then 23 is the only possible value of ''n''.
The earliest known statement of the
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of t ...
is by the Chinese mathematician Sun-tzu in the ''
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
congruences) is true over every
principal ideal domain. It has been generalized to any
ring, with a formulation involving
two-sided ideals.
History
The earliest known statement of the theorem, as a problem with specific numbers, appears in the 3rd-century book ''
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
Brahmagupta ( – ) was an Indian mathematician and astronomer. He is the author of two early works on mathematics and astronomy: the '' Brāhmasphuṭasiddhānta'' (BSS, "correctly established doctrine of Brahma", dated 628), a theoretical tr ...
(7th century), and appear in
Fibonacci's
Liber Abaci (1202). The result was later generalized with a complete solution called ''Da-yan-shu'' () in
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.
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
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries ...
but was in fact an ancient method that had appeared several times.
Statement
Let ''n''
1, ..., ''n''
''k'' be integers greater than 1, which are often called ''
moduli'' or ''
divisors
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
''. 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'' < ''n''
''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'' is ''a''
''i'' for every ''i''.
This may be restated as follows in terms of
congruences:
If the
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 and ''x''
2, are congruent modulo ''N'', that is, .
In
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
, the theorem is often restated as: if the ''n''
''i'' are pairwise coprime, the map
:
defines a
ring isomorphism
:
between the
ring of
integers modulo ''N'' and the
direct product
In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...
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
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrice ...
over the integers or the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s.
The theorem can also be restated in the language of
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
as the fact that the infinite
arithmetic progressions of integers form a
Helly family.
Proof
The existence and the uniqueness of the solution may be proven independently. However, the first proof of existence, given below, uses this uniqueness.
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 also divides , 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)
The map
:
maps
congruence classes modulo to sequences of congruence classes modulo . The proof of uniqueness shows that this map is
injective. As the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...
and the
codomain of this map have the same number of elements, the map is also
surjective
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element o ...
, 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, first solving the problem in the case of two moduli, and then extending this solution to the general case by
induction on the number of moduli.
Case of two moduli
We want to solve the system:
:
where
and
are
coprime.
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they ...
asserts the existence of two integers
and
such that
:
The integers
and
may be computed by the
extended Euclidean algorithm.
A solution is given by
:
Indeed,
:
implying that
The second congruence is proved similarly, by exchanging the subscripts 1 and 2.
General case
Consider a sequence of congruence equations:
:
where the
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
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
s instead of integers.
Let
be the product of all moduli but one. As the
are pairwise coprime,
and
are coprime. Thus
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they ...
applies, and there exist integers
and
such that
:
A solution of the system of congruences is
:
In fact, as
is a multiple of
for
we have
:
for every
Computation
Consider a system of congruences:
:
where the
are
pairwise coprime, and let
In this section several methods are described for computing the unique solution for
, such that