Chinese remainder theorem: Difference between revisions

Content deleted Content added

Inline

Revision as of 21:02, 28 August 2016

The Chinese remainder theorem appears in Gauss's 1801 book *Disquisitiones Arithmeticae*.^[1]

The Chinese remainder theorem is a theorem of number theory, which states that, if one knows the remainders of the 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.

This theorem has this name because it is a theorem about remainders, which was first discovered in the 3rd century AD by the Chinese mathematician Sun Tzu.

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.

History

The earliest known statement of the theorem, as a problem with specific numbers, appears in the 3rd-century book Sunzi's Mathematical Classic (孫子算經) by the Chinese mathematician Sun Tzu:^[2]

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? ^[3]

Sun Tzu's work contains neither a proof nor a full algorithm.^[4] What amounts to an algorithm for solving this problem was described by Aryabhata (6th century).^[5] Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).^[6] The result was later generalized with a complete solution called Dayanshu (大衍術) in Qin Jiushao's 1247 Mathematical Treatise in Nine Sections (數書九章, Shushu Jiuzhang).^[7]

The notion of congruences was first introduced and used by Gauss in his Disquisitiones Arithmeticae of 1801.^[8] 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."^[9] 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.^[10]

Theorem statement

Let $n 1, ..., 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 1, ..., a k$ are integers such that $0 \leq a i < n i$ for every $i$ , then there is one and only one integer $x$ , such that $0 \leq 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 term of congruences: If the $n i$ are pairwise coprime, and if $a 1, ..., a k$ are any integers, then there exists an integer $x$ such that

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

and any two such $x$ are congruent modulo $N$ .^[11]

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

x\operatorname {mod} N\quad \mapsto \quad (x\operatorname {mod} n_{1},\ldots ,x\operatorname {mod} n_{k})

defined a ring isomorphism^[12]

{\mathbb {Z}}/N{\mathbb {Z}}\cong {\mathbb {Z}}/n_{1}{\mathbb {Z}}\times \cdots \times {\mathbb {Z}}/n_{k}{\mathbb {Z}}

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 ${\mathbb {Z}}/N{\mathbb {Z}},$ one may do the same computation independently in each ${\mathbb {Z}}/n_{i}{\mathbb {Z}}$ 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 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.^[13]

Proof

The existence and the uniqueness of the solution may be proved independently. However the first proof of existence, given below, uses the uniqueness.

Uniqueness

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$ divides also $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$ .

Existence (first proof)

The map

x\mapsto (x\operatorname {mod} n_{1},\ldots ,x\operatorname {mod} 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 (constructive proof)

Existence may be established by an explicit construction of $x$ .^[14] This construction may be split in 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.

Case of two moduli

We want to solve the system

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

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

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

m_{1}n_{1}+m_{2}n_{2}=1.

The integers $m_{1}$ and $m_{2}$ may be computed by Extended Euclidean algorithm.

A solution is given by

x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.

In fact

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

This shows that $x\equiv a_{1}{\pmod {n_{1}}}.$ The second congruence is proved similarly, by exchanging the indices.

General case

Let us consider a sequence of congruence equations

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

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

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

As the other $n_{i}$ are coprime with $n_{1}n_{2},$ this reduces solving the initial problem of $k$ equations to a similar problem with $k-1$ 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 $N_{i}=N/n_{i}$ be the product of all moduli but one. As the $n_{i}$ are pairwise coprime, $N_{i}$ and $n_{i}$ are coprime. Thus Bézout's identity applies, and there exist integers $M_{i}$ and $m_{i}$ such that

M_{i}N_{i}+m_{i}n_{i}=1.

A solution of the system of congruences is

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

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

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

for every $i.$

Finding the solution

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

{\begin{aligned}x&\equiv 0{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 4{\pmod {5}}\end{aligned}}

Brute-force approach

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

x \in {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57}

x \in {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59}

x \in {4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59}

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

x \in {39}

This solution is modulo 60, hence all solutions are expressed as

x\equiv 39{\pmod {60}}

Exhaustive search

As the result must be a nonnegative integer less than the product of moduli (here 60), a simple method consists in considering successively the integers up to 60, and computing the remainders of the division by 3, 4, 5, until getting the result (here 39).

However, one may obtain the result faster by considering only the integers, which are congruent to 4 modulo 5 (the largest modulus); that is 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.

Using the existence construction

Bézout's identity for 3 and 4 is

1\times 4+(-1)\times 3=1.

Putting this in the formula given for proving the existence gives

0\times 4+-3\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

5\times 5+(-2)\times 12=1.

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

25\times 3-24\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.

Over principal ideal domains

In § Theorem statement, the Chinese remainder theorem has been stated in three different ways: in terms of remainders, of congruences and of a ring isomorphism. The statement in terms of remainders does not apply, in general to principal ideal domains, as remainders are not defined in such rings. However, the two other version make sense over a principal ideal domain $R$ : it suffices to replace "integer" by "element of the domain", and ${\mathbb {Z}}$ by $R$ . These two versions of the theorem are true in this context, because the proofs (except for the first existence proof), are based on Euclid's lemma and Bézout's identity, which are true over every principal domain.

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

Over univariate polynomial rings and Euclidean domains

The statement in terms of remainders given in § Theorem statement cannot be generalized to any principal ideal domain, but its generalization to Euclidean domains is straightforward. The univariate polynomials over a field is the typical example of a Euclidean domain, which is not the integers. therefore, we state the theorem for the case of a ring of univariate domain $R=K[X]$ over a field $K.$ For getting the theorem for a general Euclidean domain, it suffices to replace the degree by the Euclidean function of the Euclidean domain.

The Chinese remainder theorem for polynomials is thus: Let $P_{i}(X)$ (the moduli) be, for $i =1, ..., k$ , pairwise coprime polynomials in $R=K[X]$ . Let $d_{i}=\deg P_{i}$ be the degree of $P_{i}(X)$ , and $D$ be the sum of the $d_{i}.$ If $A_{i}(X),\ldots ,A_{k}(X)$ are polynomials such that $A_{i}(X)=0$ or $\deg A_{i}<d_{i}$ for every $i$ , then, there is one and only one polynomial $P(X)$ , such that $\deg P<D$ and the remainder of the Euclidean division of $P(X)$ by $P_{i}(X)$ is $A_{i}(X)$ for every $i$ .

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.

Thus, we want to find a polynomial $P(X)$ , which satisfies the congruences

P(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},

for $i=1,\ldots ,k.$

Let us consider the polynomials

{\begin{aligned}Q(X)&=\prod _{i=1}^{k}P_{i}(X)\\Q_{i}(X)&={\frac {Q(X)}{P_{i}(X)}}.\end{aligned}}

The partial fraction decomposition of $1/Q(X)$ gives $k$ polynomials $S_{i}(X)$ with degrees $\deg S_{i}(X)<d_{i},$ such that

{\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {S_{i}(X)}{Q_{i}(X)}},

and thus

1=\sum _{i=1}^{k}S_{i}(X)Q_{i}(X).

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

\sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X).

In fact, we have

\sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X)=A_{i}(X)+\sum _{j=1}^{k}(A_{j}(X)-A_{i}(X))S_{j}(X)Q_{j}(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},

for $1\leq i\leq k.$

This solution may have a degree larger that $\textstyle D=\sum _{i=1}^{k}d_{i}.$ The unique solution of degree less than $D$ may be deduced by considering the remainder $B_{i}(X)$ of the Euclidean division of $A_{i}(X)S_{i}(X)$ by $P_{i}(X).$ This solution is

P(X)=\sum _{i=1}^{k}B_{i}(X)Q_{i}(X).

Lagrange interpolation

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

P_{i}(X)=X-x_{i}.

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

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

P(x_{i})=A_{i},

for every $i$ .

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

{\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}

The partial fraction decomposition of $1/Q(X)$ is

{\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 $\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-X_{i})}}={\frac {\textstyle \sum _{i=1}^{k}Q_{i}(X)/Q_{i}(x_{i})}{Q(X)}},$ and the numerator is equal to one, as being a polynomial of degree less than k, which takes the value one for $k$ different values of $X.$

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

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

Hermite interpolation

Hermite interpolation is an application of 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 $x_{1},\ldots ,x_{k}$ be $k$ elements of the ground field $K,$ and, for $i=1,\ldots ,k,$ let $a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}$ be the values of the first $r_{i}$ derivatives of the sought polynomial at $x_{i}$ (including the 0th derivative, which is the value of the polynomial itself). The problem is to find a polynomial $P(X)$ such that its jth derivative takes the value $a_{i,j}$ at $x_{i},$ for $i=1,\ldots ,k$ and $j=0,\ldots ,r_{j}.$

Let us consider the polynomial

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

This is the Taylor expansion at $x_{i},$ up to the order $r_{i},$ of the unknown polynomial $P(X).$ Therefore, we must have

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

The Chinese remainder theorem asserts that there exists exactly one polynomial of degree less than the sum of the $r_{i},$ which satisfies these $k$ congruences.

There are several ways for computing the solution $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).

Generalization to arbitrary rings

The Chinese remainder theorem can be generalized to any ring, by using coprime ideals (also called comaximal ideals). Two ideals $I$ and $J$ are coprime if there are elements $i\in I$ and $j\in J$ such that $i+j=1.$ This relation plays the role of Bézout's identity in the proofs related to this generalization, which, otherwise are very similar. The generalization may be stated as follows.^[15]

Let $I 1, ..., I k$ be two-sided ideals of a ring $R$ that are pairwise coprime, and $I$ be their intersection. Then we have the isomorphism

{\begin{aligned}R/I&\to R/I_{1}\times \cdots \times R/I_{k}\\x\operatorname {mod} I&\mapsto (x\operatorname {mod} I_{1},\cdots ,x\operatorname {mod} I_{k}),\end{aligned}}

between the quotient ring $R/I$ and the direct product of the $R/I_{i},$ where " $x\operatorname {mod} I$ " denotes the image of the element $x$ in the quotient ring defined by the ideal $I.$ Moreover, if $R$ is commutative, then the ideal intersection $I$ is equal to the product of the ideals $R/I_{i}:$

I=I_{1}\cap I_{2}\cap \ldots \cap I_{k}=I_{1}I_{2}\cdots I_{k}

Applications

Sequence numbering

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.

Fast Fourier transform

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 $n_{1}n_{2}$ to the computation of two fast Fourier transforms of smaller sizes $n_{1}$ and $n_{2}$ (providing that $n_{1}$ and $n_{2}$ are coprime).

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

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

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 \in I$ of distinct monoid homomorphisms $f i : M \to k$ is linearly independent. In other words, every family $(α i) i \in I$ of elements $α i \in k$ satisfying

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

must be equal to the family $(0) i \in 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 \to k$ to $k$ -algebra homomorphisms $F i : k [M] \to 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 \in I; i \neq j$ the two $k$ -linear maps $F i : k [M] \to k$ and $F j : k [M] \to 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 \neq j$ . The Chinese Remainder Theorem (for general rings) yields an isomorphism:

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

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

Consequently, the map

{\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 \to F i (k [M]) = k,$ the map $Φ$ corresponds to:

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

Now,

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