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 earliest known statement of the theorem 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 commutative ring, with a formulation involving ideals.

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:[1]

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?[2]

Sun-tzu's work contains neither a proof nor a full algorithm.[3] What amounts to an algorithm for solving this problem was described by Aryabhata (6th century).[4] Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).[5] 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)[6] which was translated into English in early 19th century by British missionary Alexander Wylie.[7]

The notion of congruences was first introduced and used by Gauss in his Disquisitiones Arithmeticae of 1801.[9] 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."[10] Gauss introduces a procedure for solving the problem that had already been used by Euler but was in fact an ancient method that had appeared several times.[11]

Let n1, ..., nk be integers greater than 1, which are often called moduli or divisors. Let us denote by N the product of the ni.

The Chinese remainder theorem asserts that if the ni are pairwise coprime, and if a1, ..., ak are integers such that 0 ≤ ai < ni 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 ni is ai for every i.

This may be restated as follows in term of congruences: If the ni are pairwise coprime, and if a1, ..., ak are any integers, then the system

has a solution, and any two solutions, say x1 and x2, are congruent modulo N, that is, x1x2 (mod N).[12]

In abstract algebra, the theorem is often restated as: if the ni are pairwise coprime, the map

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.[14]

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 x and y are both solutions to all the congruences. As x and y give the same remainder, when divided by ni, their difference xy is a multiple of each ni. As the ni are pairwise coprime, their product N divides also xy, and thus x and y are congruent modulo N. If x and y are supposed to be non negative and less than N (as in the first statement of the theorem), then their difference may be a multiple of N only if x = y.

maps congruence classes modulo N to sequences of congruence classes modulo ni. 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 may be established by an explicit construction of x.[15] 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 induction on the number of moduli.

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.

It is easy to check whether a value of x is a solution: it suffices to compute the remainder of the Euclidean division of x by each ni. Thus, to find the solution, it suffices to check successively the integers from 0 to N until finding the solution.

Although very simple, this method is very inefficient. For the simple example considered here, 40 integers (including 0) have to be checked for finding the solution, which is 39. This is an exponential time algorithm, as the size of the input is, up to a constant factor, the number of digits of N, and the average number of operations is of the order of N.

Therefore, this method is rarely used, neither for hand-written computation nor on computers.

The smallest two solutions, 23 and 128, of the original formulation of the Chinese remainder theorem problem found using a sieve
14 + 5 = 19 mod 4 → 3. OK, continue by considering remainders modulo 3 and adding 5×4 = 20 each time

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.

For more than two moduli, the method for two moduli allows the replacement of any two congruences by a single congruence modulo the product of the moduli. Iterating this process provides eventually the solution with a complexity, which is quadratic in the number of digits of the product of all moduli. This quadratic time complexity does not depend on the order in which the moduli are regrouped. One may regroup the two first moduli, then regroup the resulting modulus with the next one, and so on. This strategy is the easiest to implement, but it also requires more computation involving large numbers.

Another strategy consists in partitioning the moduli in pairs whose product have comparable sizes (as much as possible), applying, in parallel, the method of two moduli to each pair, and iterating with a number of moduli approximatively divided by two. This method allows an easy parallelization of the algorithm. Also, if fast algorithms (that is algorithms working in quasilinear time) are used for the basic operations, this method provides an algorithm for the whole computation that works in quasilinear time.

On the current example (which has only three moduli), both strategies are identical and work as follows.

for a solution of the two first congruences, the other solutions being obtained by adding to −9 any multiple of 3×4 = 12. One may continue with any of these solutions, but the solution 3 = −9 +12 is smaller (in absolute value) and thus leads probably to an easier computation

The other solutions are obtained by adding any multiple of 3×4×5 = 60, and the smallest positive solution is −21 + 60 = 39.

The system of congruences solved by the Chinese remainder theorem may be rewritten as a :

However, in general, the theorem is only an existence theorem and does not provide any way for computing the solution, unless one has an algorithm for computing the coefficients of Bézout's identity.

The construction of the solution may be done as in § Existence (constructive proof) or § Existence (direct proof). However, the latter construction may be simplified by using, as follows, partial fraction decomposition instead of extended Euclidean algorithm.

Then a solution of the simultaneous congruence system is given by the polynomial

A special case of Chinese remainder theorem for polynomials is Lagrange interpolation. For this, consider k monic polynomials of degree one:

Lagrange interpolation formula is exactly the result, in this case, of the above construction of the solution. More precisely, let

In fact, reducing the right-hand side to a common denominator one gets

Using the above general formula, we get the Lagrange interpolation formula:

Hermite interpolation is an application of the Chinese remainder theorem for univariate polynomials, which may involve moduli of arbitrary degrees (Lagrange interpolation involves only moduli of degree one).

The problem consists of finding a polynomial of the least possible degree, such that the polynomial and its first derivatives take given values at some fixed points.

This defines an integer, as g divides both m and n. Otherwise, the proof is very similar to that for coprime moduli.

The Chinese remainder theorem has been used to construct a Gödel numbering for sequences, which is involved in the proof of Gödel's incompleteness theorems.

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 range ambiguity resolution techniques used with medium pulse repetition frequency radar can be seen as a special case of the Chinese remainder theorem.

Note that these observations are pivotal for constructing the ring of profinite integers, which is given as an inverse limit of all such maps.

Dedekind's theorem on the linear independence of characters. Let M be a monoid and k an integral domain, viewed as a monoid by considering the multiplication on k. Then any finite family fi )iI of distinct monoid homomorphisms  fi : Mk is linearly independent. In other words, every family (αi)iI of elements αik satisfying

Proof. 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  fi : Mk to k-algebra homomorphisms Fi : k[M] → k, where k[M] is the monoid ring of M over k. Then, by linearity, the condition

Next, for i, jI; ij the two k-linear maps Fi : k[M] → k and Fj : k[M] → k are not proportional to each other. Otherwise  fi  and  fj  would also be proportional, and thus equal since as monoid homomorphisms they satisfy:  fi (1) = 1 =  fj (1), which contradicts the assumption that they are distinct.

Therefore, the kernels Ker Fi and Ker Fj are distinct. Since k[M]/Ker FiFi(k[M]) = k is a field, Ker Fi is a maximal ideal of k[M] for every iI. Because they are distinct and maximal the ideals Ker Fi and Ker Fj are coprime whenever ij. The Chinese Remainder Theorem (for general rings) yields an isomorphism:

is surjective. Under the isomorphisms k[M]/Ker FiFi(k[M]) = k, the map Φ corresponds to:

for every vector (ui)iI in the image of the map ψ. Since ψ is surjective, this means that