Chinese remainder theorem

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 theorem is sometimes called Sunzi's theorem. Both names of the theorem refer to its earliest known statement that appeared in Sunzi Suanjing, a Chinese manuscript written during the 3rd to 5th century CE. This first statement was restricted to the following example:
If one knows 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 with no other information, one can determine the remainder of n divided by 105 without knowing the value of n. In this example, the remainder is 23. Moreover, this remainder is the only possible positive value of n that is less than 105.
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 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 problem appears in the 5th-century book Sunzi Suanjing by the Chinese mathematician Sunzi:
Sunzi's work would not be considered a theorem by modern standards; it only gives one particular problem, without showing how to solve it, much less any proof about the general case or a general algorithm for solving it. An algorithm for solving this problem was described by Aryabhata. Special cases of the Chinese remainder theorem were also known to Brahmagupta and appear in Fibonacci's Liber Abaci. The result was later generalized with a complete solution called Da-yan-shu in Qin Jiushao's 1247 Mathematical Treatise in Nine Sections which was translated into English in early 19th century by British missionary Alexander Wylie.
File:Disqvisitiones-800.jpg|thumb|The Chinese remainder theorem appears in Gauss's 1801 book Disquisitiones Arithmeticae.
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.

Statement

Let n₁,..., n_k be integers greater than 1, which are often called moduli or 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₁,..., 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₁,..., a_k are any integers, then the system
has a solution, and any two solutions, say x₁ and x₂, 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 of 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. 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.

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 , 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 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, 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 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 polynomials 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 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 and these methods are applied on the example
Several methods of computation are presented. The two first ones are useful for small examples, but become very inefficient when the product is large. The third one uses the existence proof given in. It is the most convenient when the product is large, or for computer computation.

Systematic search

It is easy to check whether a value of is a solution: it suffices to compute the remainder of the Euclidean division of by each. Thus, to find the solution, it suffices to check successively the integers from to until finding the solution.
Although very simple, this method is very inefficient. For the simple example considered here, integers have to be checked for finding the solution, which is. This is an exponential time algorithm, as the size of the input is, up to a constant factor, the number of digits of, and the average number of operations is of the order of.
Therefore, this method is rarely used, neither for hand-written computation nor on computers.

Search by sieving

The search of the solution may be made dramatically faster by sieving. For this method, we suppose, without loss of generality, that . This implies that the solution belongs to the arithmetic progression
By testing the values of these numbers modulo one eventually finds a solution of the two first congruences. Then the solution belongs to the arithmetic progression
Testing the values of these numbers modulo and continuing until every modulus has been tested eventually yields the solution.
This method is faster if the moduli have been ordered by decreasing value, that is if For the example, this gives the following computation. We consider first the numbers that are congruent to 4 modulo 5, which are 4,,,... For each of them, compute the remainder by 4 until getting a number congruent to 3 modulo 4. Then one can proceed by adding at each step, and computing only the remainders by 3. This gives
This method works well for hand-written computation with a product of moduli that is not too big. However, it is much slower than other methods, for very large products of moduli. Although dramatically faster than the systematic search, this method also has an exponential time complexity and is therefore not used on computers.