Chinese remainder theorem

The Chinese remainder theorem was proved by Gauss with his 1801 book Disquisitiones Arithmeticae.

The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra. It was first published in the 3rd to 5th centuries by the Chinese mathematician Sun Tzu.

In its basic form, the Chinese remainder theorem will determine a number n that, when divided by some given divisors, leaves given remainders. For example, what is the lowest number n that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2?

Theorem statement

The original form of the theorem, which is contained in the 5th-century book Sunzi's Mathematical Classic (孫子算經) by the Chinese mathematician Sun Tzu and later generalized with a complete solution called Dayanshu (大衍術) in Qin Jiushao's 1247 Mathematical Treatise in Nine Sections (數書九章, Shushu Jiuzhang), is a statement about simultaneous congruences.

Suppose n₁, ..., n_k are positive integers that are pairwise coprime. Then, for any given sequence of integers a₁, ..., a_k, there exists an integer x solving the following system of simultaneous congruences.

$\begin{cases} x \equiv a_1 & \pmod{n_1} \\ \quad \cdots \\ x \equiv a_k &\pmod{n_k} \end{cases}$

Furthermore, all solutions x of this system are congruent modulo the product, N = n₁ ... n_k. Hence

$x \equiv y \pmod{n_i}, \quad 1 \leq i \leq k \qquad \Longleftrightarrow \qquad x \equiv y \pmod{N}.$

Sometimes, the simultaneous congruences can be solved even if the n_i are not pairwise coprime. A solution x exists if and only if:

$a_i \equiv a_j \pmod{\gcd(n_i,n_j)} \qquad \text{for all }i\text{ and }j$

All solutions x are then congruent modulo the least common multiple of the n_i.

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; see Kak 1986). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).

A modern restatement of the theorem in algebraic language is that for a positive integer with prime factorization

$n = p_1^{r_1}\cdots p_k^{r_k}$

we have the isomorphism between a ring and the direct product of its prime power parts:

$\mathbf{Z}/n\mathbf{Z} \cong \mathbf{Z}/p_1^{r_1}\mathbf{Z} \times \cdots \times \mathbf{Z}/p_k^{r_k}\mathbf{Z}$

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 (Duchet 1995).

Existence and uniqueness

The existence and uniqueness of the solution can easily be seen through a non-constructive argument:

There are N = n₁·…·n_k different k-tuples of remainders. Let us call this set R. On the other hand, N = #{1, ..., N}, and each element of {1, ..., N} corresponds to an element of R. Can two numbers a, b ∈ {1, ..., N}, correspond to the same member of R? That is, can they have the same set of remainders when divided by n₁, ..., n_k? If they did then a − b would be divisible by each n_i. Since the n_i are relatively prime, a − b would be divisible by their product: N. But, as 0 < | a − b | < N, this can't be, so this function {1, ..., N} → R is one-to-one. Since #{1, ..., N} = #R, it must be onto as well. Thus we have established the existence of a bijection.

Existence can be seen by an explicit construction of x. Let [a⁻¹]_b denote the multiplicative inverse of a (mod b) given by the Extended Euclidean algorithm. It is defined exactly when a and b are coprime; the following construction explains why this condition is needed.

Case of two equations (k = 2)

Consider the system:

$\begin{cases} x \equiv a_1 & \pmod{n_1} \\ x \equiv a_2 & \pmod{n_2} \end{cases}$

Since gcd(n₁, n₂) = 1, Bézout's identity implies:

$n_2 \left [n_2^{-1} \right ]_{n_1} + n_1 \left [n_1^{-1} \right ]_{n_2} = 1$

This is true because we are using the inverses provided by the Extended Euclidean algorithm; for any other inverses, this would not necessarily be true, but still be valid (mod n₁n₂).

Multiplying both sides by x, we get

$x = x n_2 \left [n_2^{-1} \right ]_{n_1} + x n_1 \left [n_1^{-1} \right ]_{n_2}$

If we take the congruence modulo n₁ for the right-hand-side expression, it is readily seen that

$x \underbrace{n_2 \left [n_2^{-1} \right ]_{n_1}}_1 + x \underbrace{n_1}_0 \left [n_1^{-1} \right ]_{n_2} \equiv x \times 1 + x \times 0 \times \left [n_1^{-1} \right ]_{n_2} \equiv x \pmod {n_1}$

But we know that x ≡ a₁ (mod n₁), thus this suggests that the coefficient of the first term on the right-hand-side expression can be replaced by a₁. Similarly, we can show that the coefficient of the second term can be substituted by a₂. We can now define the value

$x \equiv a_1 n_2 \left [n_2^{-1} \right ]_{n_1} + a_2 n_1 \left [n_1^{-1} \right ]_{n_2}$

and it is seen to satisfy both congruences, for example:

$a_1 n_2 \left [n_2^{-1} \right ]_{n_1} + a_2 n_1 \left [n_1^{-1} \right ]_{n_2} \equiv a_1 \times 1 + a_2 \times 0 \times \left [n_1^{-1} \right ]_{n_2} \equiv a_1 \pmod {n_1}$

General case

The same type of construction works in the general case of k congruence equations. Let N = n₁ ... n_k be the product of every modulus then define

$x := \left[\sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}\right]_{N}$

and this is seen to satisfy the system of congruences by a similar calculation as before.

Finding the solution with basic algebra and modular arithmetic

For example, consider the problem of finding an integer x such that

$\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{4} \\ x \equiv 1 \pmod{5} \end{cases}$

Brute-force approach

A brute-force approach converts these congruences into sets and writes the elements out to the product of 3×4×5 = 60 (the solutions modulo 60 for each congruence):

x ∈ {2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, ...}

x ∈ {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, ...}

x ∈ {1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, 61, 66, 71, 76, 81, 86, 91, 96, ...}

To find an x that satisfies all three congruences, intersect the three sets to get:

x ∈ {11, 71, ...}

Which can be expressed as

$x \equiv 11 \pmod{60}$

Algebraic approach

Another way to find a solution is with basic algebra, modular arithmetic, and stepwise substitution.

We start by translating these congruences into equations for some t, s, and u:

$\begin{cases}x = 2 + 3t \\ x = 3 + 4s \\ x = 1 + 5u \end{cases}$

Start by substituting the x from the first equation into the second congruence:

$\begin{align} 2 + 3t &\equiv 3 &&\pmod{4} \\ 3t &\equiv 1 && \pmod{4} \\ t &\equiv (3)^{-1} \equiv 3 &&\pmod{4} \end{align}$

meaning that t = 3 + 4s for some integer s. Substitute t into the first equation:

$x = 2 + 3t = 2 + 3(3 + 4s) = 11 + 12s$

Substitute this x into the third congruence:

$\begin{align} 11 + 12s &\equiv 1 && \pmod{5} \\ 1 + 2s &\equiv 1 &&\pmod{5} \\ 2s &\equiv 0 &&\pmod{5} \end{align}$

meaning that s = 0 + 5u for some integer u. Finally,

$x = 11 + 12s = 11 + 12(5u) = 11 + 60u$

So, we have solutions {11, 71, 131, 191, ...}.

Notice that 60 = lcm(3,4,5). If the moduli are pairwise coprime (as they are in this example), the solutions will be congruent modulo their product.

A constructive algorithm to find the solution

The following algorithm only applies if the n_i are pairwise coprime. (For simultaneous congruences when the moduli are not pairwise coprime, the method of successive substitution can often yield solutions.)

Suppose, as above, that a solution is required for the system of congruences:

$x \equiv a_i \pmod{n_i}, \qquad i = 1, \cdots, k.$

Define: N = n₁ ... n_k. For each i, the integers n_i and N/n_i are coprime. Using the extended Euclidean algorithm we can find r_i, s_i ∈ Z such that r_in_i + s_iN/n_i = 1. Substitute e_i for s_iN/n_i, to arrive at: r_in_i + e_i = 1. So the remainder of e_i divided by n_i is 1. On the other hand, e_i = s_iN/n_i, guarantees that n_j divides e_i for j ≠ i. To summarize:

$e_i \equiv \begin{cases} 1 \pmod{n_i} \\ 0 \pmod{n_j} & j \ne i \end{cases}$

Because of this, and the multiplication rules allowed in congruences, one solution to the system of simultaneous congruences is:

$x = \sum_{i=1}^k a_i e_i$

For example, consider the problem of finding an integer x such that

$\begin{cases} x \equiv 2 & \pmod{3} \\ x \equiv 3 & \pmod{4} \\ x \equiv 1 & \pmod{5} \end{cases}$

Using the extended Euclidean algorithm, for x modulo 3 and 20 [4 × 5], we find (−13) × 3 + 2 × 20 = 1; i.e., e₁ = 40. For x modulo 4 and 15 [3 × 5], we get (−11) × 4 + 3 × 15 = 1, i.e. e₂ = 45. Finally, for x modulo 5 and 12 [3 × 4], we get 5 × 5 + (−2) × 12 = 1, i.e. e₃ = −24. A solution x is therefore 2 × 40 + 3 × 45 + 1 × (−24) = 191. All other solutions are congruent to 191 modulo 60, [3 × 4 × 5], which means they are all congruent to 11 modulo 60.

Or in words:

1. Find a number e_i that gives modulo 1 for a particular divisor, but is divisible by all other divisors (coprime, in this case).
2. Multiply the remainder (of the original number N to this particular divisor). Repeat with all the divisors.
3. Sum all these products together.
4. Divide the sum by the LCM of all the divisors. N shares the modulo with the final remainder.

Thus, we have e_i values of 40 (divisible by 4 and 5; gives 1 for mod 3), 45 (for mod 4) and 36 (for mod 5). Multiplying by the given remainders 2, 3 and 1 yields 80, 135 and 36 respectively. The sum, 251, is then divided by 60, yielding remainder 11.

Note: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of e₁ = −20, e₂ = −15, and e₃ = −24. These sets however will produce the same solution; i.e., (−20)2 + (−15)3 + (−24)1 = −109 ≡ 11 (mod 60).

Using the same principle, the answer to Sun Tzu's original question is therefore 23, using e_i values of 70, 21 and 15 for divisors 3, 5, 7: (70)2 + (21)3 + (15)2 = 233 ≡ 23 (mod 105).

Statement for principal ideal domains

Chinese Remainder Theorem for Principal Ideal Domains. Let R be principal ideal domain. If u₁, ..., u_k are pairwise coprime elements of R where u = u₁...u_k, then the quotient ring R/uR and the product ring R/u₁R × ... × R/u_kR are isomorphic via the following map:

$\begin{align} f: R/uR &\to R/u_1R \times \cdots \times R/u_k R \\ f(x + uR) &= (x + u_1R, \ldots, x + u_kR) \end{align}$

This statement is a straightforward generalization of the above theorem about integer congruences: Z is a principal ideal domain, the surjectivity of the map f shows that every system of congruences of the form

$x \equiv a_i \pmod{u_i} \qquad 1 \leq i \leq k$

can be solved for x, and the injectivity of the map f shows that all the solutions x are congruent modulo u.

Proof. This map is well-defined and a homomorphism of rings. An inverse homomorphism can be constructed as follows, showing that it is in fact an isomorphism. For each i, the elements u_i and u/u_i are coprime, and therefore there exist elements r and s in R with

$r u_i + s u/u_i = 1$

Set e_i = su/u_i. Then it is clear that

$e_i \equiv \delta_{ij} \pmod{u_jR}.$

Thus the inverse of f is the map

$\begin{align} g: R/u_1R \times \cdots \times R/u_kR &\to R/uR \\ g(a_1 + u_1R, \ldots, a_k + u_kR) &= \sum_{i=1}^k a_i e_i + uR \end{align}$

Statement for general rings

The general form of the Chinese remainder theorem, which implies all the statements given above, can be formulated for commutative rings and ideals.

Chinese Remainder Theorem for Commutative Rings. If R is a commutative ring and I₁, ..., I_k are ideals of R that are pairwise coprime (meaning I_i + I_j = R for all i ≠ j), then the product I of these ideals is equal to their intersection, and the quotient ring R/I is isomorphic to the product ring R/I₁ × ... × R/I_k via the isomorphism

$\begin{align} f\colon R/I &\to R/I_1 \times \cdots \times R/I_k \\ f(x + I) &= (x + I_1, \cdots, x + I_k) \end{align}$

Here is a version of the theorem where R is not required to be commutative:

Chinese Remainder Theorem for Noncommutative Rings. Let R be any ring with 1 (not necessarily commutative) and I₁, ..., I_k be pairwise coprime 2-sided ideals. Then the canonical ring homomorphism R → R/I₁ × ... × R/I_k is onto, with kernel I₁ ∩ ... ∩ I_k. Hence, $\scriptstyle R/(I_1 \,\cap\, \cdots \,\cap\, I_k) \,\simeq\, R/I_1 \,\times\, \cdots \,\times\, R/I_k$.

Applications

Sequence numbering

The Chinese remainder theorem can be used to construct an elegant Gödel numbering for sequences, which is needed to prove Gödel's incompleteness theorems.

Fast Fourier transform

The Good-Thomas fast Fourier transform algorithm exploits a re-indexing of the data based on the Chinese remainder theorem. The Prime-factor FFT algorithm contains an implementation.

Encryption

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.

Range ambiguity resolution

Main article: range ambiguity resolution

The range ambiguity resolution techniques used with medium pulse repetition frequency radar can be seen as a special case of the Chinese remainder theorem.

Hermite interpolation

The General Hermite Interpolation Problem. Given r complex points ("interpolation nodes") λ₁, …, λ_r and complex data {a_j,k: 1 ≤ j ≤ r, 0 ≤ k < ν_j}, find P(x) ∈ C[x] such that:

$P^{(k)}(\lambda_j) = a_{j, k}\qquad 1 \leq j \leq r, \quad 0 \leq k < \nu_j.$

Solution. Introducing the polynomials

$A_j(x) := \sum_{k=0}^{\nu_j - 1}\frac{a_{j, k}}{k!}(x - \lambda_j)^k$

the problem may be equivalently reformulated as a system of r simultaneous congruences:

$P(x) \equiv A_j(x) \pmod {(x - \lambda_j)^{\nu_j}}, \qquad 1 \leq j \leq r$

By the Chinese remainder theorem in the principal ideal domain C[x], there is a unique polynomial P(x) such that:

$\deg(P) < n := \sum_j\nu_j.$

A direct construction, in analogy with the above proof for the integer number case, can be performed as follows. Define the polynomials

$\begin{align} Q &= \prod_{i=1}^{r}(x - \lambda_i)^{\nu_i} \\ Q_j &= \frac{Q}{(x - \lambda_j)^{\nu_j}} \end{align}$

The partial fraction decomposition of 1/Q gives r polynomials S_j with degrees deg(S_j) < ν_j such that

$\frac{1}{Q} = \sum_{i=1}^{r} \frac{S_i}{(x - \lambda_i)^{\nu_i}}$

so that

$1 = \sum_{i=1}^{r}S_i Q_i.$

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

$\sum_{i=1}^r A_i S_i Q_i = A_j + \sum_{i=1}^{r}(A_i - A_j) S_i Q_i \equiv A_j\pmod{(x - \lambda_j)^{\nu_j}}\qquad 1 \leq j \leq r$

and the minimal degree solution is this one reduced modulo Q, that is the unique with degree less than n.

Dedekind's theorem

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

$\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

$\sum_{i\in I}\alpha_i f_i = 0,$

yields

$\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 ∈ 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:

$\begin{align} \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{align}$

where

$K = \prod_{i \in I}\mathrm{Ker} F_i = \bigcap_{i \in I}\mathrm{Ker} F_i.$

Consequently, the map

$\begin{align} \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{align}$

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

$\begin{align} \psi: k[M] &\to \prod_{i \in I}k \\ \psi(x) &= \left[F_i(x)\right]_{i \in I} \end{align}$

Now,

$\sum_{i \in I}\alpha_i F_i = 0$

yields

$\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

$\sum_{i \in I}\alpha_i u_i = 0$

for every vector

$\left(u_i\right)_{i \in I} \in \prod_{i \in I}k.$

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

Non-commutative case: a caveat

Sometimes in the commutative case, the conclusion of the Chinese Remainder Theorem is stated as R/(I₁ ... I_k) ≅ R/I₁ × ... × R/I_k. This version does not hold in the non-commutative case, since I₁ ∩ ... ∩ I_k ≠ I₁ ... I_k, as can be seen from the following case:

Proposition. Let R be the ring of non-commutative real polynomials in x and y. Let I be the principal two-sided ideal generated by x and J the principal two-sided ideal generated by xy + 1. Then I + J = R but I ∩ J ≠ IJ.

Proof. Observe that I is formed by all polynomials with an x in every term and that every polynomial in J vanishes under the substitution y = − 1/x. Then clearly p = (xy + 1)x ∈ I ∩ J. Define a "term in R", as an element of the multiplicative monoid of R generated by x and y, and its degree as the usual degree of the term after the substitution y = x. On the other hand, suppose q ∈ J. Observe that a term in q of maximum degree depends on y otherwise q under the substitution y = − 1/x can not vanish. The same happens then for an element q ∈ IJ. Note that the last y, from left to right, in a term of maximum degree in an element of IJ is preceded by more than one x. (We are counting here all the preceding xs. E.g., in x²yxyx⁵ the last y is preceded by three xs.) This proves that p = (xy + 1)x ∉ IJ since the last y in the term of maximum degree in p (xyx) is preceded by only one x. Hence I ∩ J ≠ IJ.

However, it is true in general that I + J = R implies I ∩ J = IJ + JI. To see this, note that I ∩ J = (I ∩ J)(I + J) ⊂ IJ + JI, while the opposite inclusion is obvious. Also, we have in general that, provided I₁, ..., I_m are pairwise coprime two-sided ideals in R, the natural map

$R / (I_1 \cap \cdots \cap I_m) \to R/I_1 \oplus \cdots \oplus R/I_m$

is an isomorphism. Note that I₁ ∩ ... ∩ I_m can be replaced by a sum over all orderings of I₁, ..., I_m of their product (or just a sum over enough orderings, using inductively that I ∩ J = IJ + JI for coprime ideals I, J ⊂ R).

See also

• Covering system
• Hasse principle
• Residue number system
• Secret sharing using the Chinese remainder theorem

References

• . See Section 31.5: The Chinese remainder theorem, pp. 873–876.
• . See in particular Section 2.5, "Helly Property", pp. 393–394.
• . See Section 4.3.2 (pp. 286–291), exercise 4.6.2–3 (page 456).

External links

• "Chinese Remainder Theorem" by Ed Pegg, Jr., Wolfram Demonstrations Project, 2007.
• Weisstein, Eric W., "Chinese Remainder Theorem", MathWorld.
• C# program and discussion at codeproject
• University of Hawaii System CRT by Lee Lady
• Full text of the Sunzi Suanjing (Chinese) — Chinese Text Project