Chinese remainder theorem

Suppose that x and y are both solutions to all the congruences. As x and y give the same remainder, when divided by n_i, their difference x − y is a multiple of each n_i. As the n_i are pairwise coprime, their product N also divides x − y, 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.

The map

${\displaystyle x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})}$

maps congruence classes modulo N to sequences of congruence classes modulo n_i. 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, 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.

We want to solve the system:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}}$

where ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ are coprime.

Bézout's identity asserts the existence of two integers ${\displaystyle m_{1}}$ and ${\displaystyle m_{2}}$ such that

${\displaystyle m_{1}n_{1}+m_{2}n_{2}=1.}$

The integers ${\displaystyle m_{1}}$ and ${\displaystyle m_{2}}$ may be computed by the extended Euclidean algorithm.

A solution is given by

${\displaystyle x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.}$

Indeed,

${\displaystyle {\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}}$

implying that ${\displaystyle x\equiv a_{1}{\pmod {n_{1}}}.}$ The second congruence is proved similarly, by exchanging the subscripts 1 and 2.

Consider a sequence of congruence equations:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}$

where the ${\displaystyle n_{i}}$ are pairwise coprime. The two first equations have a solution ${\displaystyle a_{1,2}}$ 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

${\displaystyle x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.}$

As the other ${\displaystyle n_{i}}$ are coprime with ${\displaystyle n_{1}n_{2},}$ this reduces solving the initial problem of k equations to a similar problem with ${\displaystyle k-1}$ equations. Iterating the process, one gets eventually the solutions of the initial problem.

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 ${\displaystyle N_{i}=N/n_{i}}$ be the product of all moduli but one. As the ${\displaystyle n_{i}}$ are pairwise coprime, ${\displaystyle N_{i}}$ and ${\displaystyle n_{i}}$ are coprime. Thus Bézout's identity applies, and there exist integers ${\displaystyle M_{i}}$ and ${\displaystyle m_{i}}$ such that

${\displaystyle M_{i}N_{i}+m_{i}n_{i}=1.}$

A solution of the system of congruences is

${\displaystyle x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.}$

In fact, as ${\displaystyle N_{j}}$ is a multiple of ${\displaystyle n_{i}}$ for ${\displaystyle i\neq j,}$ we have

${\displaystyle x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},}$

for every ${\displaystyle i.}$

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 n_i. 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

The search of the solution may be made dramatically faster by sieving. For this method, we suppose, without loss of generality, that ${\displaystyle 0\leq a_{i}<n_{i}}$ (if it were not the case, it would suffice to replace each ${\displaystyle a_{i}}$ by the remainder of its division by ${\displaystyle n_{i}}$). This implies that the solution belongs to the arithmetic progression

${\displaystyle a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots }$

By testing the values of these numbers modulo ${\displaystyle n_{2},}$ one eventually finds a solution ${\displaystyle x_{2}}$ of the two first congruences. Then the solution belongs to the arithmetic progression

${\displaystyle x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots }$

Testing the values of these numbers modulo ${\displaystyle n_{3},}$ 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 ${\displaystyle n_{1}>n_{2}>\cdots >n_{k}.}$ For the example, this gives the following computation. We consider first the numbers that are congruent to 4 modulo 5 (the largest modulus), which are 4, 9 = 4 + 5, 14 = 9 + 5, ... For each of them, compute the remainder by 4 (the second largest modulus) until getting a number congruent to 3 modulo 4. Then one can proceed by adding 20 = 5 × 4 at each step, and computing only the remainders by 3. This gives

4 mod 4 → 0. Continue

4 + 5 = 9 mod 4 →1. Continue

9 + 5 = 14 mod 4 → 2. Continue

14 + 5 = 19 mod 4 → 3. OK, continue by considering remainders modulo 3 and adding 5 × 4 = 20 each time

19 mod 3 → 1. Continue

19 + 20 = 39 mod 3 → 0. OK, this is the result.

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.

The constructive existence proof shows that, in the case of two moduli, the solution may be obtained by the computation of the Bézout coefficients of the moduli, followed by a few multiplications, additions and reductions modulo ${\displaystyle n_{1}n_{2}}$ (for getting a result in the interval ${\displaystyle (0,n_{1}n_{2}-1)}$). As the Bézout's coefficients may be computed with the extended Euclidean algorithm, the whole computation, at most, has a quadratic time complexity of ${\displaystyle O((s_{1}+s_{2})^{2}),}$ where ${\displaystyle s_{i}}$ denotes the number of digits of ${\displaystyle n_{i}.}$

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.

Bézout's identity for 3 and 4 is

${\displaystyle 1\times 4+(-1)\times 3=1.}$

Putting this in the formula given for proving the existence gives

${\displaystyle 0\times 1\times 4+3\times (-1)\times 3=-9}$

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

Bézout identity for 5 and 3 × 4 = 12 is

${\displaystyle 5\times 5+(-2)\times 12=1.}$

Applying the same formula again, we get a solution of the problem:

${\displaystyle 5\times 5\times 3+12\times (-2)\times 4=-21.}$

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 system of linear Diophantine equations:

${\displaystyle {\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}}$

where the unknown integers are ${\displaystyle x}$ and the ${\displaystyle x_{i}.}$ Therefore, every general method for solving such systems may be used for finding the solution of Chinese remainder theorem, such as the reduction of the matrix of the system to Smith normal form or Hermite normal form. However, as usual when using a general algorithm for a more specific problem, this approach is less efficient than the method of the preceding section, based on a direct use of Bézout's identity.

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

${\displaystyle P_{i}(X)=X-x_{i}.}$

They are pairwise coprime if the ${\displaystyle x_{i}}$ are all different. The remainder of the division by ${\displaystyle P_{i}(X)}$ of a polynomial ${\displaystyle P(X)}$ is ${\displaystyle P(x_{i})}$, by the polynomial remainder theorem.

Now, let ${\displaystyle A_{1},\ldots ,A_{k}}$ be constants (polynomials of degree 0) in ${\displaystyle K.}$ Both Lagrange interpolation and Chinese remainder theorem assert the existence of a unique polynomial ${\displaystyle P(X),}$ of degree less than ${\displaystyle k}$ such that

${\displaystyle P(x_{i})=A_{i},}$

for every ${\displaystyle i.}$

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

${\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}}$

The partial fraction decomposition of ${\displaystyle {\frac {1}{Q(X)}}}$ is

${\displaystyle {\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}.}$

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

${\displaystyle \sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}={\frac {1}{Q(X)}}\sum _{i=1}^{k}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}},}$

and the numerator is equal to one, as being a polynomial of degree less than ${\displaystyle k,}$ which takes the value one for ${\displaystyle k}$ different values of ${\displaystyle X.}$

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

${\displaystyle P(X)=\sum _{i=1}^{k}A_{i}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}.}$

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.

More precisely, let ${\displaystyle x_{1},\ldots ,x_{k}}$ be ${\displaystyle k}$ elements of the ground field ${\displaystyle K,}$ and, for ${\displaystyle i=1,\ldots ,k,}$ let ${\displaystyle a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}}$ be the values of the first ${\displaystyle r_{i}}$ derivatives of the sought polynomial at ${\displaystyle x_{i}}$ (including the 0th derivative, which is the value of the polynomial itself). The problem is to find a polynomial ${\displaystyle P(X)}$ such that its j th derivative takes the value ${\displaystyle a_{i,j}}$ at ${\displaystyle x_{i},}$ for ${\displaystyle i=1,\ldots ,k}$ and ${\displaystyle j=0,\ldots ,r_{j}.}$

Consider the polynomial

${\displaystyle P_{i}(X)=\sum _{j=0}^{r_{i}-1}{\frac {a_{i,j}}{j!}}(X-x_{i})^{j}.}$

This is the Taylor polynomial of order ${\displaystyle r_{i}-1}$ at ${\displaystyle x_{i}}$, of the unknown polynomial ${\displaystyle P(X).}$ Therefore, we must have

${\displaystyle P(X)\equiv P_{i}(X){\pmod {(X-x_{i})^{r_{i}}}}.}$

Conversely, any polynomial ${\displaystyle P(X)}$ that satisfies these ${\displaystyle k}$ congruences, in particular verifies, for any ${\displaystyle i=1,\ldots ,k}$

${\displaystyle P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}}$

therefore ${\displaystyle P_{i}(X)}$ is its Taylor polynomial of order ${\displaystyle r_{i}-1}$ at ${\displaystyle x_{i}}$, that is, ${\displaystyle P(X)}$ solves the initial Hermite interpolation problem. The Chinese remainder theorem asserts that there exists exactly one polynomial of degree less than the sum of the ${\displaystyle r_{i},}$ which satisfies these ${\displaystyle k}$ congruences.

There are several ways for computing the solution ${\displaystyle P(X).}$ One may use the method described at the beginning of § Over univariate polynomial rings and Euclidean domains. One may also use the constructions given in § Existence (constructive proof) or § Existence (direct proof).

Let ${\displaystyle I_{1},I_{2},\dots ,I_{k}}$ be pairwise coprime two-sided ideals with ${\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}$ and

${\displaystyle \varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})}$

be the isomorphism defined above. Let ${\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)}$ be the element of ${\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})}$ whose components are all 0 except the i th which is 1, and ${\displaystyle e_{i}=\varphi ^{-1}(f_{i}).}$

The ${\displaystyle e_{i}}$ are central idempotents that are pairwise orthogonal; this means, in particular, that ${\displaystyle e_{i}^{2}=e_{i}}$ and ${\displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$ for every i and j. Moreover, one has ${\textstyle e_{1}+\cdots +e_{n}=1,}$ and ${\displaystyle I_{i}=R(1-e_{i}).}$

In summary, this generalized Chinese remainder theorem is the equivalence between giving pairwise coprime two-sided ideals with a zero intersection, and giving central and pairwise orthogonal idempotents that sum to 1.[19]

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 prime-factor FFT algorithm (also called Good-Thomas algorithm) uses the Chinese remainder theorem for reducing the computation of a fast Fourier transform of size ${\displaystyle n_{1}n_{2}}$ to the computation of two fast Fourier transforms of smaller sizes ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ (providing that ${\displaystyle n_{1}}$ and ${\displaystyle n_{2}}$ are coprime).

Most implementations of RSA use the Chinese remainder theorem during signing of HTTPS certificates and during decryption.

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.

Given a surjection ${\displaystyle \mathbb {Z} /n\to \mathbb {Z} /m}$ of finite abelian groups, we can use the Chinese remainder theorem to give a complete description of any such map. First of all, the theorem gives isomorphisms

${\displaystyle {\begin{aligned}\mathbb {Z} /n&\cong \mathbb {Z} /p_{n_{1}}^{a_{1}}\times \cdots \times \mathbb {Z} /p_{n_{i}}^{a_{i}}\\\mathbb {Z} /m&\cong \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}}$

where ${\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}}$. In addition, for any induced map

${\displaystyle \mathbb {Z} /p_{n_{k}}^{a_{k}}\to \mathbb {Z} /p_{m_{l}}^{b_{l}}}$

from the original surjection, we have ${\displaystyle a_{k}\geq b_{l}}$ and ${\displaystyle p_{n_{k}}=p_{m_{l}},}$ since for a pair of primes ${\displaystyle p,q}$, the only non-zero surjections

${\displaystyle \mathbb {Z} /p^{a}\to \mathbb {Z} /q^{b}}$

can be defined if ${\displaystyle p=q}$ and ${\displaystyle a\geq b}$.

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 ( f_i )_i∈I of distinct monoid homomorphisms  f_i : M → k is linearly independent. In other words, every family (α_i)_i∈I of elements α_i ∈ k satisfying

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}$

must be equal to the family (0)_i∈I.

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

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0,}$

yields

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0.}$

Next, for i, j ∈ I; i ≠ j the two k-linear maps F_i : k[M] → k and F_j : k[M] → k are not proportional to each other. Otherwise  f_i  and  f_j  would also be proportional, and thus equal since as monoid homomorphisms they satisfy:  f_i (1) = 1 =  f_j (1), which contradicts the assumption that they are distinct.

Therefore, the kernels Ker F_i and Ker F_j are distinct. Since k[M]/Ker F_i ≅ F_i (k[M]) = k is a field, Ker F_i is a maximal ideal of k[M] for every i in I. Because they are distinct and maximal the ideals Ker F_i and Ker F_j are coprime whenever i ≠ j. The Chinese Remainder Theorem (for general rings) yields an isomorphism:

${\displaystyle {\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\phi (x+K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

where

${\displaystyle K=\prod _{i\in I}\mathrm {Ker} F_{i}=\bigcap _{i\in I}\mathrm {Ker} F_{i}.}$

Consequently, the map

${\displaystyle {\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\Phi (x)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

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

${\displaystyle {\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}}$

Now,

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0}$

yields

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

for every vector (u_i)_i∈I in the image of the map ψ. Since ψ is surjective, this means that

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

for every vector

${\displaystyle \left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k.}$

Consequently, (α_i)_i∈I = (0)_i∈I. QED.