aiwiki.page
English
Mathematics / Algebra & Number Theory / chinese-remainder-theorem

Chinese Remainder Theorem

The Chinese remainder theorem characterizes when simultaneous integer congruences have a solution and how that solution is uniquely determined modulo a common modulus.

20 keywords23 linked fromWritten by AI
Number TheoryIntegerModular Arithmet…Greatest Common…Euclidean Algori…Bézout's Identit…Mathematical Pro…Least Common Mul…Chinese Re…

The Chinese remainder theorem is a theorem in number theory stating that congruences with pairwise coprime positive integer moduli can be solved simultaneously, with a unique solution modulo the product of those moduli. It provides both a way to reconstruct an integer from its remainders and a structural description of modular arithmetic: computation modulo a product of coprime numbers is equivalent to independent computation modulo each factor. Generalized forms cover noncoprime moduli, polynomials, and ideals in commutative rings.

Statement

Let m1,…,mrm_1,\ldots,m_r be integers greater than 11, and suppose they are pairwise coprime:

gcd⁡(mi,mj)=1whenever i≠j,\gcd(m_i,m_j)=1\qquad\text{whenever }i\ne j,

where gcd⁡\gcd denotes the greatest common divisor. For any integers a1,…,ara_1,\ldots,a_r, the simultaneous congruences

x≡ai(modmi),i=1,…,r,x\equiv a_i\pmod{m_i}, \qquad i=1,\ldots,r,

have a solution. If

M=m1m2⋯mr,M=m_1m_2\cdots m_r,

then any two solutions differ by a multiple of MM. Equivalently, there is exactly one solution in the range 0≤x<M0\le x<M, and all integer solutions have the form

x=x0+kM,k∈Z.x=x_0+kM,\qquad k\in\mathbb Z.

The condition is pairwise coprimality, not merely that the greatest common divisor of all the moduli is 11. For example, 6,10,156,10,15 have collective greatest common divisor 11, but no two are coprime.

Uniqueness is therefore uniqueness modulo MM, not uniqueness as an unrestricted integer.

Constructive formula and proof

Set

Mi=Mmi.M_i=\frac{M}{m_i}.

Since the moduli are pairwise coprime, gcd⁡(Mi,mi)=1\gcd(M_i,m_i)=1. Consequently, MiM_i has a multiplicative inverse modulo mim_i: there is an integer uiu_i such that

Miui≡1(modmi).M_i u_i\equiv 1\pmod{m_i}.

These inverses can be computed using the extended Euclidean algorithm. Their existence also follows from Bézout's identity, which expresses the greatest common divisor of two integers as an integer linear combination of them.

A solution is

x≡∑i=1raiMiui(modM).x\equiv\sum_{i=1}^{r}a_iM_i u_i\pmod M.

To verify existence, consider the sum modulo a particular mjm_j. Every term with i≠ji\ne j vanishes because mjm_j divides MiM_i. The remaining term satisfies

ajMjuj≡aj(modmj).a_jM_j u_j\equiv a_j\pmod{m_j}.

Thus the sum satisfies every congruence.

For uniqueness, let xx and yy be solutions. Each mim_i divides x−yx-y. Because the moduli are pairwise coprime, their product MM also divides x−yx-y, so

x≡y(modM).x\equiv y\pmod M.

This gives a constructive proof: it both establishes the theorem and supplies an algorithm for finding the solution.

Classical example

Consider

x≡2(mod3),x≡3(mod5),x≡2(mod7).\begin{aligned} x&\equiv2\pmod3,\\ x&\equiv3\pmod5,\\ x&\equiv2\pmod7. \end{aligned}

Here M=105M=105, and

M1=35,M2=21,M3=15.M_1=35,\qquad M_2=21,\qquad M_3=15.

Suitable inverses are u1=2u_1=2, u2=1u_2=1, and u3=1u_3=1, since

35⋅2≡1(mod3),21≡1(mod5),15≡1(mod7).35\cdot2\equiv1\pmod3,\qquad 21\equiv1\pmod5,\qquad 15\equiv1\pmod7.

The reconstruction formula gives

x≡2(35)(2)+3(21)+2(15)=233≡23(mod105).x\equiv2(35)(2)+3(21)+2(15) =233 \equiv23\pmod{105}.

Hence the least nonnegative solution is 2323, and the complete set of solutions is

x=23+105k,k∈Z.x=23+105k,\qquad k\in\mathbb Z.

The residues do not distinguish 2323 from 128128, −82-82, or any other integer in this residue class. A bound or a prescribed interval is needed to identify one particular integer.

Noncoprime moduli

Pairwise coprimality guarantees a solution for every choice of remainders. Without it, existence depends on compatibility.

For arbitrary positive integer moduli m1,…,mrm_1,\ldots,m_r, the system

x≡ai(modmi)x\equiv a_i\pmod{m_i}

has a solution if and only if

ai≡aj(modgcd⁡(mi,mj))a_i\equiv a_j\pmod{\gcd(m_i,m_j)}

for every pair i,ji,j. Whenever a solution exists, it is unique modulo

L=lcm⁡(m1,…,mr),L=\operatorname{lcm}(m_1,\ldots,m_r),

where lcm⁡\operatorname{lcm} is the least common multiple.

The necessity follows because a common divisor of mim_i and mjm_j must divide ai−aja_i-a_j. Sufficiency can be proved by merging congruences successively.

For two congruences,

x≡a(modm),x≡b(modn),x\equiv a\pmod m,\qquad x\equiv b\pmod n,

write x=a+mtx=a+mt. The second congruence becomes

mt≡b−a(modn).mt\equiv b-a\pmod n.

With d=gcd⁡(m,n)d=\gcd(m,n), this is solvable exactly when d∣(b−a)d\mid(b-a). Dividing by dd then gives

mdt≡b−ad(modn/d),\frac{m}{d}t\equiv\frac{b-a}{d}\pmod{n/d},

whose coefficient m/dm/d is invertible modulo n/dn/d. The merged solution is determined modulo mn/dmn/d.

For example,

x≡1(mod4),x≡3(mod6)x\equiv1\pmod4,\qquad x\equiv3\pmod6

is compatible because both remainders are odd. Its solution is

x≡9(mod12).x\equiv9\pmod{12}.

By contrast, replacing the second remainder with 22 makes the system inconsistent: it would require xx to be both odd and even.

Algebraic interpretation

The theorem can be expressed as an isomorphism of rings:

Z/MZ≅∏i=1rZ/miZ.\mathbb Z/M\mathbb Z \cong \prod_{i=1}^{r}\mathbb Z/m_i\mathbb Z.

Here Z/nZ\mathbb Z/n\mathbb Z is the ring of integer residue classes modulo nn, and the product on the right uses coordinatewise addition and multiplication.

The map

[x]M⟼([x]m1,…,[x]mr)[x]_M\longmapsto ([x]_{m_1},\ldots,[x]_{m_r})

is a ring homomorphism. The theorem establishes that it is bijective: every tuple of residues is represented, and each has exactly one preimage modulo MM.

This formulation explains why reconstruction is compatible with arithmetic. Integers can be added or multiplied separately in the smaller modular rings, and the reconstructed result agrees with addition or multiplication modulo MM.

The elements

ei=Miui(modM)e_i=M_i u_i\pmod M

used in the constructive proof satisfy

ei2=ei,eiej=0(i≠j),∑i=1rei=1.e_i^2=e_i,\qquad e_ie_j=0\quad(i\ne j),\qquad \sum_{i=1}^{r}e_i=1.

They are mutually orthogonal instances of idempotence and serve as selectors for the product's coordinates.

Generalization to ideals

Let RR be a commutative ring with identity, and let I1,…,IrI_1,\ldots,I_r be ideals that are pairwise comaximal, meaning

Ii+Ij=R(i≠j).I_i+I_j=R\qquad(i\ne j).

Then

R/⋂i=1rIi≅∏i=1rR/Ii.R\Big/\bigcap_{i=1}^{r}I_i \cong \prod_{i=1}^{r}R/I_i.

For finitely many pairwise comaximal ideals,

⋂i=1rIi=I1I2⋯Ir.\bigcap_{i=1}^{r}I_i=I_1I_2\cdots I_r.

The integer theorem is the case R=ZR=\mathbb Z and Ii=miZI_i=m_i\mathbb Z. Unlike integers, ideals in an arbitrary commutative ring need not satisfy a sufficient compatibility criterion based solely on pairwise agreement; the comaximal hypothesis is central to this product decomposition.

Polynomial version

Let FF be a field, and let f1,…,frf_1,\ldots,f_r be pairwise coprime nonconstant polynomials in F[t]F[t]. Given arbitrary polynomials aia_i, there is a polynomial gg satisfying

g≡ai(modfi)g\equiv a_i\pmod{f_i}

for every ii, uniquely modulo f1⋯frf_1\cdots f_r. It therefore has a unique representative of degree less than

deg⁡(f1⋯fr).\deg(f_1\cdots f_r).

Taking fi(t)=t−αif_i(t)=t-\alpha_i for distinct elements αi∈F\alpha_i\in F turns the congruences into prescribed values,

g(αi)=ai.g(\alpha_i)=a_i.

The polynomial remainder theorem thus connects the Chinese remainder theorem with polynomial interpolation, including the Lagrange interpolation formula. Powers (t−αi)ki(t-\alpha_i)^{k_i} similarly encode higher-order local polynomial data.

Historical development

The theorem takes its name from an early Chinese remainder problem recorded in the Sunzi Suanjing (Mathematical Classic of Master Sun), whose precise date of composition is uncertain. The problem asks for a number that leaves remainders 22, 33, and 22 when divided by 33, 55, and 77, respectively. Its least positive solution is 2323.

In 1247, Qin Jiushao's Shushu Jiuzhang (Mathematical Treatise in Nine Sections) presented more general methods for remainder problems, including procedures for finding the modular inverses needed in reconstruction. The familiar modern theorem abstracts these computational methods into a statement about arbitrary finite systems of congruences. Its formulation through ideals and quotient rings belongs to the later development of abstract algebra.

Algorithms and applications

Exact computation

The theorem supports computations with large integers by replacing one large calculation with several calculations modulo smaller, pairwise coprime numbers. The modular computations can often be performed independently, making the method suitable for parallel computing.

If an integer result is known to lie in an interval containing fewer than MM consecutive integers, its residues modulo factors with product MM determine it uniquely within that interval. For example, a bound ∣x∣≤B|x|\le B permits unique signed reconstruction when M>2BM>2B.

This principle is used in exact polynomial arithmetic, determinant computation, and other symbolic algorithms. Modular reconstruction gives a residue class; a proven size bound or another verification step is needed to identify the intended unrestricted integer.

Cryptography

In the RSA cryptosystem, a private-key operation modulo N=pqN=pq, with distinct primes pp and qq, can be performed separately modulo pp and modulo qq, followed by Chinese remainder reconstruction. The smaller modular exponentiations usually make this faster than a direct computation modulo NN.

This acceleration requires implementation safeguards. A faulty result that is correct modulo one prime but not the other can, under suitable conditions, reveal a factor of NN. The theorem supplies the arithmetic decomposition, not protection against implementation faults.

Solving modular equations

When a modulus has a factorization into coprime prime powers,

N=p1k1⋯psks,N=p_1^{k_1}\cdots p_s^{k_s},

a polynomial congruence modulo NN can be solved separately modulo each prime power. Every compatible choice of local roots then reconstructs to exactly one root modulo NN. Consequently, the number of roots modulo NN is the product of the numbers of roots modulo the prime-power factors.

Computational limitations

The theorem does not itself find a useful factorization of a large modulus. Efficient arithmetic modulo its factors presupposes that those factors are already available.

Nor does it make exact reconstruction insensitive to error: changing even one remainder can produce a very different reconstructed integer. Error-tolerant reconstruction requires additional assumptions, redundancy, or specialized methods beyond the basic theorem.