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 ''Sunzi Suanjing, 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 Modular arithmetic#Congruence, congruences) is true over every principal ideal domain. It has been generalized to any ring (mathematics), ring, with a formulation involving two-sided ideals.

_{1}, ..., ''n''_{''k''} be integers greater than 1, which are often called ''modular arithmetic, moduli'' or ''Euclidean division, 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 ≤ ''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 term of congruence relation, congruences:
If the ''n''_{''i''} are pairwise coprime, and if ''a''_{1}, ..., ''a''_{''k''} are any integers, then the system
:$\backslash begin\; x\; \&\backslash equiv\; a\_1\; \backslash pmod\; \backslash \backslash \; \&\backslash ,\backslash ,\backslash ,\backslash vdots\; \backslash \backslash \; x\; \&\backslash equiv\; a\_k\; \backslash pmod,\; \backslash end$
has a solution, and any two solutions, say ''x''_{1} and ''x''_{2}, are congruent modulo ''N'', that is, .
In abstract algebra, the theorem is often restated as: if the ''n''_{''i''} are pairwise coprime, the map
:$x\; \backslash bmod\; N\; \backslash ;\backslash mapsto\backslash ;(x\; \backslash bmod\; n\_1,\backslash ,\; \backslash ldots,\backslash ,\; x\; \backslash bmod\; n\_k)$
defines a ring isomorphism
:$\backslash mathbb/N\backslash mathbb\; \backslash cong\; \backslash mathbb/n\_1\backslash mathbb\; \backslash times\; \backslash cdots\; \backslash times\; \backslash mathbb/n\_k\backslash mathbb$
between the ring (mathematics), ring of integers modulo n, 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 $\backslash mathbb/N\backslash mathbb,$ one may do the same computation independently in each $\backslash mathbb/n\_i\backslash mathbb$ 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.

pp. 393–394

* * * * * * * * * *

Full text of the Sun-tzu Suan-ching

(Chinese) Chinese Text Project {{authority control Articles containing proofs Chinese mathematical discoveries, Sun, Master Commutative algebra Modular arithmetic Theorems in number theory

History

The earliest known statement of the theorem, as a problem with specific numbers, appears in the 3rd-century book ''Sunzi Suanjing, Sun-tzu Suan-ching'' by the Chinese mathematician Sun-tzu: 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). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202). The result was later generalized with a complete solution called ''Da-yan-shu'' () in Qin Jiushao, Ch'in Chiu-shao's 1247 ''Mathematical Treatise in Nine Sections'' (, ''Shu-shu Chiu-chang'') which was translated into English in early 19th century by British missionary Alexander Wylie (missionary), Alexander Wylie. 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''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 divides also , and thus and are congruent modulo . If and are supposed to be non negative and less than (as in the first statement of the theorem), then their difference may be a multiple of only if .Existence (first proof)

The map :$x\; \backslash bmod\; N\; \backslash mapsto\; (x\; \backslash bmod\; n\_1,\; \backslash ldots,\; x\backslash bmod\; n\_k)$ maps congruence classes modulo to sequences of congruence classes modulo . The proof of uniqueness shows that this map is injective. As the domain of a function, 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, firstly by solving the problem in the case of two moduli, and the second one by extending this solution to the general case by mathematical induction, induction on the number of moduli.Case of two moduli

We want to solve the system: :$\backslash begin\; x\; \&\backslash equiv\; a\_1\; \backslash pmod\; \backslash \backslash \; x\; \&\backslash equiv\; a\_2\; \backslash pmod\; ,\; \backslash end$ 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\_1n\_1+m\_2n\_2=1.$ The integers $m\_1$ and $m\_2$ may be computed by the extended Euclidean algorithm. A solution is given by :$x\; =\; a\_1m\_2n\_2+a\_2m\_1n\_1.$ Indeed, :$\backslash begin\; x\&=a\_1m\_2n\_2+a\_2m\_1n\_1\backslash \backslash \; \&=a\_1(1\; -\; m\_1n\_1)\; +\; a\_2m\_1n\_1\; \backslash \backslash \; \&=a\_1\; +\; (a\_2\; -\; a\_1)m\_1n\_1,\; \backslash end$ implying that $x\; \backslash equiv\; a\_1\; \backslash pmod\; .$ The second congruence is proved similarly, by exchanging the subscripts 1 and 2.General case

Consider a sequence of congruence equations: :$\backslash begin\; x\; \&\backslash equiv\; a\_1\; \backslash pmod\; \backslash \backslash \; \&\backslash vdots\; \backslash \backslash \; x\; \&\backslash equiv\; a\_k\; \backslash pmod,\; \backslash end$ where the $n\_i$ are pairwise coprime. The two first equations have a solution $a\_$ 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\; \backslash equiv\; a\_\; \backslash pmod.$ As the other $n\_i$ are coprime with $n\_1n\_2,$ this reduces solving the initial problem of 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\_iN\_i\; +\; m\_in\_i=1.$ A solution of the system of congruences is :$x=\backslash sum\_^k\; a\_iM\_iN\_i.$ In fact, as $N\_j$ is a multiple of $n\_i$ for $i\backslash neq\; j,$ we have :$x\; \backslash equiv\; a\_iM\_iN\_i\; \backslash equiv\; a\_i(1-m\_in\_i)\; \backslash equiv\; a\_i\; \backslash pmod,$ for every $i.$Computation

Consider a system of congruences: :$\backslash begin\; x\; \&\backslash equiv\; a\_1\; \backslash pmod\; \backslash \backslash \; \&\backslash vdots\; \backslash \backslash \; x\; \&\backslash equiv\; a\_k\; \backslash pmod,\; \backslash \backslash \; \backslash end$ where the $n\_i$ are pairwise coprime, and let $N=n\_1\; n\_2\backslash cdots\; n\_k.$ In this section several methods are described for computing the unique solution for $x$, such that $0\backslash le\; x,\; math>\; and\; these\; methods\; are\; applied\; on\; the\; example:\; :$ \backslash begin\; x\; \backslash equiv\; 0\; \backslash pmod\; 3\; \backslash \backslash \; x\; \backslash equiv\; 3\; \backslash pmod\; 4\; \backslash \backslash \; x\; \backslash equiv\; 4\; \backslash pmod\; 5.\; \backslash end$$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 (including ) 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, thatUsing the existence construction

The #Existence (constructive proof), constructive existence proof shows that, in the #Case of two moduli, 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 $n\_1n\_2$ (for getting a result in the interval $(0,\; n\_1n\_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 $O((s\_1+s\_2)^2),$ where $s\_i$ denotes the number of digits of $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 :$1\backslash times\; 4\; +\; (-1)\backslash times\; 3\; =\; 1.$ Putting this in the formula given for proving the existence gives :$0\backslash times\; 1\backslash times\; 4\; +\; 3\backslash times\; (-1)\backslash times\; 3\; =-9$ for a solution of the two first congruences, the other solutions being obtained by adding to −9 any multiple of . One may continue with any of these solutions, but the solution is smaller (in absolute value) and thus leads probably to an easier computation Bézout identity for 5 and 3×4 = 12 is :$5\backslash times\; 5\; +(-2)\backslash times\; 12\; =1.$ Applying the same formula again, we get a solution of the problem: :$25\backslash times\; 3\; -24\backslash times\; 4\; =\; -21.$ The other solutions are obtained by adding any multiple of , and the smallest positive solution is .As a linear Diophantine system

The system of congruences solved by the Chinese remainder theorem may be rewritten as a Diophantine equation#System of linear Diophantine equations, system of simultaneous linear Diophantine equations: :$\backslash begin\; x\; \&=\; a\_1\; +x\_1n\_1\backslash \backslash \; \&\backslash vdots\; \backslash \backslash \; x\; \&=a\_k+x\_kn\_k,\; \backslash end$ where the unknown integers are $x$ and the $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.Over principal ideal domains

In , 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 versions make sense over a principal ideal domain : it suffices to replace "integer" by "element of the domain" and $\backslash mathbb\; Z$ by . 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 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 cannot be generalized to any principal ideal domain, but its generalization to Euclidean domains is straightforward. The univariate polynomials over a field (mathematics), 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 , pairwise coprime polynomials in $R=K[X]$. Let $d\_i\; =\backslash deg\; P\_i$ be the degree of $P\_i(X)$, and $D$ be the sum of the $d\_i.$ If $A\_i(X),\; \backslash ldots,A\_k(X)$ are polynomials such that $A\_i(X)=0$ or $\backslash deg\; A\_imath>\; for\; every\; ,\; then,\; there\; is\; one\; and\; only\; one\; polynomial$ P(X)$,\; such\; that$ \backslash deg\; Pmath>\; and\; the\; remainder\; of\; the\; Euclidean\; division\; of$ P(X)$by$ P\_i(X)$is$ A\_i(X)$for\; every\; .\; The\; construction\; of\; the\; solution\; may\; be\; done\; as\; in\; or\; .\; 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)\backslash equiv\; A\_i(X)\; \backslash pmod\; ,$for$ i=1,\backslash ldots,k.$Consider\; the\; polynomials\; :$ \backslash begin\; Q(X)\; =\; \backslash prod\_^P\_i(X)\; \backslash \backslash \; Q\_i(X)\; =\; \backslash frac.\; \backslash end$The\; partial\; fraction\; decomposition\; of$ 1/Q(X)$gives\; polynomials$ S\_i(X)$with\; degrees$ \backslash deg\; S\_i(X)\; d\_i,$such\; that\; :$ \backslash frac\; =\; \backslash sum\_^k\; \backslash frac,$and\; thus\; :$ 1\; =\; \backslash sum\_^S\_i(X)\; Q\_i(X).$Then\; a\; solution\; of\; the\; simultaneous\; congruence\; system\; is\; given\; by\; the\; polynomial\; :$ \backslash sum\_^k\; A\_i(X)\; S\_i(X)\; Q\_i(X).$In\; fact,\; we\; have\; :$ \backslash sum\_^k\; A\_i(X)\; S\_i(X)\; Q\_i(X)=\; A\_i(X)+\; \backslash sum\_^(A\_j(X)\; -\; A\_i(X))\; S\_j(X)\; Q\_j(X)\; \backslash equiv\; A\_i(X)\backslash pmod,$for$ 1\; \backslash leq\; i\; \backslash leq\; k.$This\; solution\; may\; have\; a\; degree\; larger\; that$ D=\backslash sum\_^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)=\backslash sum\_^k\; B\_i(X)\; Q\_i(X).$$>$Lagrange interpolation

A special case of Chinese remainder theorem for polynomials is Lagrange interpolation. For this, consider 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,\; \backslash 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 :$\backslash begin\; Q(X)\; \&=\; \backslash prod\_^(X-x\_i)\; \backslash \backslash [6pt]\; Q\_i(X)\; \&=\; \backslash frac.\; \backslash end$ The partial fraction decomposition of $\backslash frac$ is :$\backslash frac\; =\; \backslash sum\_^k\; \backslash frac.$ In fact, reducing the right-hand side to a common denominator one gets :$\backslash sum\_^k\; \backslash frac=\; \backslash frac\; \backslash sum\_^k\; \backslash frac,$ 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)=\backslash sum\_^k\; A\_i\backslash frac.$Hermite interpolation

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 $x\_1,\; \backslash ldots,\; x\_k$ be $k$ elements of the ground field (mathematics), field $K,$ and, for $i=1,\backslash ldots,\; k,$ let $a\_,\; a\_,\; \backslash ldots,\; a\_$ 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 ''j''th derivative takes the value $a\_$ at $x\_i,$ for $i=1,\backslash ldots,k$ and $j=0,\backslash ldots,r\_j.$ Consider the polynomial :$P\_i(X)\; =\; \backslash sum\_^\backslash frac(X\; -\; x\_i)^j.$ This is the Taylor polynomial of order $r\_i-1$ at $x\_i$, of the unknown polynomial $P(X).$ Therefore, we must have :$P(X)\backslash equiv\; P\_i(X)\; \backslash pmod\; .$ Conversely, any polynomial $P(X)$ that satisfies these $k$ congruences, in particular verifies, for any $i=1,\; \backslash ldots,\; k$ :$P(X)=\; P\_i(X)\; +o(X-x\_i)^$ therefore $P\_i(X)$ is its Taylor polynomial of order $r\_i\; -\; 1$ at $x\_i$, that is, $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 $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 . One may also use the constructions given in or .Generalization to non-coprime moduli

The Chinese remainder theorem can be generalized to non-coprime moduli. Let $m,\; n,\; a,\; b$ be any integers, let $g\; =\; \backslash gcd(m,n)$, and consider the system of congruences: :$\backslash begin\; x\; \&\backslash equiv\; a\; \backslash pmod\; m\; \backslash \backslash \; x\; \&\backslash equiv\; b\; \backslash pmod\; n,\; \backslash end$ If $a\; \backslash equiv\; b\; \backslash pmod\; g$, then this system of equations has a unique solution modulo $\backslash operatorname(m,n)\; =\; mn/g$. Otherwise, it has no solutions. If we use Bézout's identity to write $g\; =\; um\; +\; vn$, then the solution is :$x\; =\; \backslash frac.$ This defines an integer, as divides both and . Otherwise, the proof is very similar to that for coprime moduli.Generalization to arbitrary rings

The Chinese remainder theorem can be generalized to any ring (mathematics), ring, by using Coprime integers#Coprimality in ring ideals, coprime ideals (also called Ideal (ring theory)#Types of ideals, comaximal ideals). Two ideals and are coprime if there are elements $i\backslash in\; I$ and $j\backslash 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. Let be two-sided ideals of a ring $R$ and let be their intersection. If the ideals are pairwise coprime, we have the ring homomorphism, isomorphism: :$\backslash begin\; R/I\; \&\backslash to\; (R/I\_1)\; \backslash times\; \backslash cdots\; \backslash times\; (R/I\_k)\; \backslash \backslash \; x\; \backslash bmod\; I\; \&\backslash mapsto\; (x\; \backslash bmod\; I\_1,\backslash ,\; \backslash ldots,\backslash ,\; x\; \backslash bmod\; I\_k),\; \backslash end$ between the quotient ring $R/I$ and the direct product of rings, direct product of the $R/I\_i,$ where "$x\; \backslash bmod\; I$" denotes the image of the element $x$ in the quotient ring defined by the ideal $I.$ Moreover, if $R$ is commutative ring, commutative, then the ideal intersection of pairwise coprime ideals is equal to their product of ideals, product; that is :$I=\; I\_1\backslash cap\; I\_2\; \backslash cap\backslash cdots\backslash cap\; I\_k=\; I\_1I\_2\backslash cdots\; I\_k,$ if and are coprime for .Interpretation in terms of idempotents

Let $I\_1,\; I\_2,\; \backslash dots,\; I\_k$ be pairwise coprime two-sided ideals with $\backslash bigcap\_^k\; I\_i\; =\; 0,$ and :$\backslash varphi:R\backslash to\; (R/I\_1)\; \backslash times\; \backslash cdots\; \backslash times\; (R/I\_k)$ be the isomorphism defined above. Let $f\_i=(0,\backslash ldots,1,\backslash ldots,\; 0)$ be the element of $(R/I\_1)\; \backslash times\; \backslash cdots\; \backslash times\; (R/I\_k)$ whose components are all except the th that is , and $e\_i=\backslash varphi^(f\_i).$ The $e\_i$ are central idempotents that are pairwise central idempotent, orthogonal; this means, in particular, that $e\_i^2=e\_i$ and $e\_ie\_j=e\_je\_i=0$ for every and . Moreover, one has $e\_1+\backslash cdots+e\_n=1,$ and $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 .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\_1n\_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 RSA (cryptosystem)#Using the Chinese remainder algorithm, 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.Decomposition of surjections of finite abelian groups

Given a Surjective function, surjection $\backslash mathbb/n\; \backslash to\; \backslash mathbb/m$ of finite Abelian group, 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$\backslash begin\; \backslash mathbb/n\; \&\backslash cong\; \backslash mathbb/p\_^\; \backslash times\; \backslash cdots\; \backslash times\; \backslash mathbb/p\_^\; \backslash \backslash \; \backslash mathbb/m\; \&\backslash cong\; \backslash mathbb/p\_^\; \backslash times\; \backslash cdots\; \backslash times\; \backslash mathbb/p\_^\; \backslash end$where $\backslash \; \backslash subseteq\; \backslash $. In addition, for any induced map

$\backslash mathbb/p\_^\; \backslash to\; \backslash mathbb/p\_^$from the original surjection, we have $a\_k\; \backslash geq\; b\_l$ and $p\_\; =\; p\_$, since for a pair of primes $p,q$, the only non-zero surjections

$\backslash mathbb/p^a\; \backslash to\; \backslash mathbb/q^b$can be defined if $p\; =\; q$ and $a\; \backslash geq\; b$. Note that these observations are pivotal for constructing the ring of Profinite integer, profinite integers, which is given as an inverse limit of all such maps.

Dedekind's theorem

Dedekind's theorem on the linear independence of characters. Let be a monoid and an integral domain, viewed as a monoid by considering the multiplication on . Then any finite family of distinct monoid homomorphisms is linearly independent. In other words, every family of elements satisfying :$\backslash sum\_\backslash alpha\_i\; f\_i\; =\; 0$ must be equal to the family . Proof. First assume that is a field, otherwise, replace the integral domain by its quotient field, and nothing will change. We can linearly extend the monoid homomorphisms to -algebra homomorphisms , where is the monoid ring of over . Then, by linearity, the condition :$\backslash sum\_\backslash alpha\_i\; f\_i\; =\; 0,$ yields :$\backslash sum\_\backslash alpha\_i\; F\_i\; =\; 0.$ Next, for the two -linear maps and are not proportional to each other. Otherwise and would also be proportional, and thus equal since as monoid homomorphisms they satisfy: , which contradicts the assumption that they are distinct. Therefore, the kernels and are distinct. Since is a field, is a maximal ideal of for every . Because they are distinct and maximal the ideals and are coprime whenever . The Chinese Remainder Theorem (for general rings) yields an isomorphism: :$\backslash begin\; \backslash phi:\; k[M]\; /\; K\; \&\backslash to\; \backslash prod\_k[M]\; /\; \backslash mathrm\; F\_i\; \backslash \backslash \; \backslash phi(x\; +\; K)\; \&=\; \backslash left(x\; +\; \backslash mathrm\; F\_i\backslash right)\_\; \backslash end$ where :$K\; =\; \backslash prod\_\backslash mathrm\; F\_i\; =\; \backslash bigcap\_\backslash mathrm\; F\_i.$ Consequently, the map :$\backslash begin\; \backslash Phi:\; k[M]\; \&\backslash to\; \backslash prod\_k[M]/\; \backslash mathrm\; F\_i\; \backslash \backslash \; \backslash Phi(x)\; \&=\; \backslash left(x\; +\; \backslash mathrm\; F\_i\backslash right)\_\; \backslash end$ is surjective. Under the isomorphisms the map corresponds to: :$\backslash begin\; \backslash psi:\; k[M]\; \&\backslash to\; \backslash prod\_k\; \backslash \backslash \; \backslash psi(x)\; \&=\; \backslash left[F\_i(x)\backslash right]\_\; \backslash end$ Now, :$\backslash sum\_\backslash alpha\_i\; F\_i\; =\; 0$ yields :$\backslash sum\_\backslash alpha\_i\; u\_i\; =\; 0$ for every vector in the image of the map . Since is surjective, this means that :$\backslash sum\_\backslash alpha\_i\; u\_i\; =\; 0$ for every vector :$\backslash left(u\_i\backslash right)\_\; \backslash in\; \backslash prod\_k.$ Consequently, . QED.See also

* Covering system * Hasse principle * Residue number systemNotes

References

* * *. See in particular Section 2.5, "Helly Property"pp. 393–394

* * * * * * * * * *

Further reading

*. See Section 31.5: The Chinese remainder theorem, pp. 873–876. * * *. See Section 4.3.2 (pp. 286–291), exercise 4.6.2–3 (page 456).External links

* * *Full text of the Sun-tzu Suan-ching

(Chinese) Chinese Text Project {{authority control Articles containing proofs Chinese mathematical discoveries, Sun, Master Commutative algebra Modular arithmetic Theorems in number theory