The Chinese Remainder Theorem

Suppose a farmer counts eggs by threes and has two left over. Then he counts them by fives and has three left over. How many eggs are there? This childlike puzzle was recorded in Chinese mathematical texts nearly two thousand years ago. It hides a deep structural fact about the integers. The question is not just "find a number." It is "understand exactly which numbers work, and why the answer is essentially unique." The Chinese Remainder Theorem answers this completely. It tells us when a system of simultaneous congruences has a solution. It tells us how many solutions there are modulo the product of the moduli. Most importantly for higher mathematics, it tells us why solving several congruences separately and solving one congruence modulo the product are the same problem in disguise. The theorem matters because it is the first deep example of a ring decomposing into a product of simpler rings. Behind the elementary arithmetic sits the statement that Z/mnZ\mathbb{Z}/mn\mathbb{Z} is isomorphic, as a ring, to Z/mZ×Z/nZ\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} whenever gcd⁡(m,n)=1\gcd(m,n)=1. This single isomorphism explains an enormous range of phenomena. It explains why Euler's totient function is multiplicative. It explains why RSA encryption can be sped up by working modulo two primes separately. It explains why polynomial interpolation and error-correcting codes can reconstruct data from redundant fragments. It also explains why the integers modulo nn split apart exactly according to the prime factorization of nn. The big picture is that congruences are not isolated puzzles but coordinates. A point in the plane is determined by its xx-coordinate and its yy-coordinate independently. Likewise, an integer modulo mnmn (with m,nm,n coprime) is determined by its residue modulo mm and its residue modulo nn. Every combination of coordinates is achievable. The Chinese Remainder Theorem is the arithmetic version of this coordinate-splitting idea. It is built on the humble but powerful machinery of Linear Congruences and Residue Classes and Complete Residue Systems. This article gives the precise statement of the theorem for two moduli. It also covers arbitrarily many pairwise coprime moduli. It gives a complete constructive proof using Bézout's identity. It includes a worked numerical example with genuinely different moduli and remainders. It gives a second worked example showing the theorem's use in the ring-isomorphism language. It offers a counterexample showing exactly what fails when coprimality is dropped. It discusses where the result is used across mathematics and computing. It closes by foreshadowing how this machinery yields the multiplicativity of Euler's totient function.

Key takeaways
  • The CRT solves systems of congruences x≡ai(modmi)x \equiv a_i \pmod{m_i} simultaneously, provided the moduli mim_i are pairwise coprime.
  • A solution always exists in this coprime case, and it is unique modulo the product M=m1m2⋯mkM = m_1 m_2 \cdots m_k.
  • The proof is constructive: it builds the solution explicitly from Bézout coefficients, so it is an algorithm, not just an existence statement.
  • Algebraically, the theorem says Z/MZ≅Z/m1Z×⋯×Z/mkZ\mathbb{Z}/M\mathbb{Z} \cong \mathbb{Z}/m_1\mathbb{Z} \times \cdots \times \mathbb{Z}/m_k\mathbb{Z} as rings.
  • Pairwise coprimality is essential: without it, systems can have no solution, or the naive product bound on solutions can fail.
  • Key idea: knowing an integer's residues modulo pairwise coprime numbers is exactly equivalent to knowing the integer modulo their product.

Where this lives today

The Chinese Remainder Theorem is a working tool across many fields, not just a historical curiosity. In cryptography, RSA decryption is commonly accelerated using the CRT: instead of computing cd  nc^d \bmod n directly for a large n=pqn=pq, one computes the exponentiation modulo pp and modulo qq separately (each roughly four times faster since the exponents and moduli are about half the bit-length) and recombines the two results via the CRT formula — a standard optimization in real-world implementations. In computer arithmetic and hardware design, "residue number systems" represent large integers as tuples of residues modulo small pairwise coprime moduli, allowing addition and multiplication to be performed in parallel, independently, per coordinate — exactly the ring-isomorphism structure of the corollary above — which speeds up digital signal processing and certain cryptographic accelerators. In coding theory, Reed–Solomon-style reconstruction and certain secret-sharing schemes (e.g. the Asmuth–Bloom scheme) use CRT-style reconstruction from partial, redundant residue information, tolerating lost or corrupted shares. In pure mathematics, the theorem is the seed of the general theory of ring decomposition via comaximal ideals in commutative algebra, and it directly implies — via the multiplicativity of the isomorphism's unit-counting — that the Multiplicativity of the Totient Function holds: since φ(n)\varphi(n) counts units in Z/nZ\mathbb{Z}/n\mathbb{Z}, and units in a product ring are exactly pairs of units, one gets φ(mn)=φ(m)φ(n)\varphi(mn)=\varphi(m)\varphi(n) for coprime m,nm,n almost for free from the CRT ring isomorphism. It also underlies interpolation-based polynomial reconstruction (the "polynomial CRT" over Euclidean domains) and appears in scheduling and calendrical calculations reminiscent of the original egg-counting puzzles.

Ask the tutor: How does the same Bézout-based construction extend to solving systems where the moduli are not pairwise coprime, using lcm\mathrm{lcm} instead of the product?

DefinitionSimultaneous congruences and their solution

Let m1,m2,…,mkm_1, m_2, \dots, m_k be positive integers and let a1,a2,…,aka_1, a_2, \dots, a_k be integers. The system of simultaneous congruences

x≡a1(modm1),x≡a2(modm2),…,x≡ak(modmk)x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \dots, \quad x \equiv a_k \pmod{m_k}

asks for an integer xx satisfying all kk congruences at once. The moduli are called pairwise coprime if gcd⁡(mi,mj)=1\gcd(m_i, m_j) = 1 for every pair i≠ji \neq j. A solution modulo MM, where M=m1m2⋯mkM = m_1 m_2 \cdots m_k, means a residue class x0+MZx_0 + M\mathbb{Z} such that every integer in that class satisfies all kk congruences, and no integer outside that class (among representatives 0,1,…,M−10,1,\dots,M-1) does.

Intuition

Think of an integer modulo mm and modulo nn as two separate "readings" of the same number, like a clock with two hands moving at different, unrelated speeds. If the speeds (moduli) share no common factor, the two hands trace out every possible combination of positions before the pattern repeats, and the pattern's full period is exactly the product of the two speeds. This is the essence of why coprimality is the right hypothesis: it guarantees no combination of readings is ever "wasted" or "unreachable," and none is ever hit twice within one full period. Picture the residues modulo 33 laid out on one axis and residues modulo 55 on another axis, forming a 3×53 \times 5 grid of 1515 cells. The Chinese Remainder Theorem says that as xx runs through 0,1,2,…,140, 1, 2, \dots, 14, the pair (remainder mod 3, remainder mod 5) visits every one of the 1515 cells in the grid exactly once — a perfect bijection between {0,…,14}\{0,\dots,14\} and the grid {0,1,2}×{0,1,2,3,4}\{0,1,2\}\times\{0,1,2,3,4\}. This bijective "unwinding" of a two-dimensional grid into a single one-dimensional cycle of length 15=3×515 = 3\times 5 is the geometric heart of the theorem.

Figure
The map x↦(x mod 3, x mod 5)x \mapsto (x \bmod 3,\ x \bmod 5) is a bijection from {0,…,14}\{0,\dots,14\} to the 3×53\times5 grid
x mod 3 (rows) vs x mod 5 (columns), x = 0..14 c=0 c=1 c=2 c=3 c=4 r=0 r=1 r=2 0 6 12 3 9 10 1 7 13 4 5 11 2 8 14 Each of x = 0,...,14 appears exactly once: a bijection onto the 3×5 grid.

The theorem

TheoremChinese Remainder Theorem

Let k≥2k \ge 2 and let m1,m2,…,mkm_1, m_2, \dots, m_k be positive integers that are pairwise coprime, meaning gcd⁡(mi,mj)=1\gcd(m_i,m_j) = 1 for all i≠ji \neq j. Let a1,a2,…,aka_1, a_2, \dots, a_k be arbitrary integers, and set

M=m1m2⋯mk.M = m_1 m_2 \cdots m_k.

Then the system of congruences

x≡a1(modm1),x≡a2(modm2),…,x≡ak(modmk)x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \dots, \quad x \equiv a_k \pmod{m_k}

has a solution x=x0∈Zx = x_0 \in \mathbb{Z}. Moreover, an integer xx satisfies all kk congruences if and only if

x≡x0(modM).x \equiv x_0 \pmod{M}.

That is, the solution set is exactly one residue class modulo MM.

LemmaTwo-modulus case

Let m,nm,n be positive integers with gcd⁡(m,n)=1\gcd(m,n)=1, and let a,b∈Za,b \in \mathbb{Z}. Then there exists x0∈Zx_0 \in \mathbb{Z} with

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

and the set of all such xx is precisely x0+mnZx_0 + mn\mathbb{Z}.

Proof

Proof of the Lemma (existence, by explicit construction from Bézout's identity). Since gcd⁡(m,n)=1\gcd(m,n) = 1, Bézout's identity (a direct consequence of the Euclidean algorithm, standard from the theory of Linear Congruences) guarantees integers u,vu, v with

um+vn=1.um + vn = 1.

Define

x0=a vn+b um.x_0 = a\, vn + b\, um.

We check the two congruences directly. Modulo mm: since um≡0(modm)um \equiv 0 \pmod m, Bézout's identity gives vn≡1(modm)vn \equiv 1 \pmod m, so

x0=a vn+b um≡a⋅1+b⋅0=a(modm).x_0 = a\,vn + b\,um \equiv a \cdot 1 + b \cdot 0 = a \pmod m.

Modulo nn: since vn≡0(modn)vn \equiv 0 \pmod n, Bézout's identity gives um≡1(modn)um \equiv 1 \pmod n, so

x0=a vn+b um≡a⋅0+b⋅1=b(modn).x_0 = a\,vn + b\,um \equiv a \cdot 0 + b \cdot 1 = b \pmod n.

Thus x0x_0 satisfies both congruences, proving existence.

Uniqueness modulo mnmn. First, every xx of the form x0+tmnx_0 + tmn for t∈Zt \in \mathbb{Z} also solves the system, since tmn≡0tmn \equiv 0 both mod mm and mod nn (as m∣mnm \mid mn and n∣mnn \mid mn), so x≡x0≡a(modm)x \equiv x_0 \equiv a \pmod m and x≡x0≡b(modn)x \equiv x_0 \equiv b \pmod n. Conversely, suppose x1x_1 is any solution, so x1≡a(modm)x_1 \equiv a \pmod m and x1≡b(modn)x_1 \equiv b \pmod n. Since x0x_0 is also a solution, subtracting gives

x1−x0≡0(modm)andx1−x0≡0(modn),x_1 - x_0 \equiv 0 \pmod m \quad \text{and} \quad x_1 - x_0 \equiv 0 \pmod n,

i.e. m∣(x1−x0)m \mid (x_1 - x_0) and n∣(x1−x0)n \mid (x_1 - x_0). Because gcd⁡(m,n)=1\gcd(m,n) = 1, we invoke the standard divisibility fact: if two coprime integers each divide an integer dd, then their product divides dd. (Proof of this sub-fact: write um+vn=1um+vn=1; then d=d(um+vn)=u(md)+v(nd)d = d(um+vn) = u(md) + v(nd)... more directly, since m∣dm \mid d write d=mcd = mc; since n∣d=mcn \mid d = mc and gcd⁡(n,m)=1\gcd(n,m)=1, Euclid's lemma gives n∣cn \mid c, so c=nec = ne and d=mned = mne, i.e. mn∣dmn \mid d.) Applying this with d=x1−x0d = x_1 - x_0 gives mn∣(x1−x0)mn \mid (x_1-x_0), i.e. x1≡x0(modmn)x_1 \equiv x_0 \pmod{mn}. This proves the solution set is exactly the residue class x0+mnZx_0 + mn\mathbb{Z}, completing the Lemma. ■\blacksquare

∎
Proof

Proof of the Theorem (induction on kk, using the Lemma as the base/inductive step). We argue by induction on the number of moduli k≥2k \ge 2. Base case k=2k=2. This is exactly the Lemma just proved: pairwise coprimality of {m1,m2}\{m_1,m_2\} is simply gcd⁡(m1,m2)=1\gcd(m_1,m_2)=1, and the Lemma produces x0x_0 solving both congruences, unique modulo m1m2=Mm_1m_2 = M. Inductive step. Suppose k≥3k \ge 3 and the theorem holds for any k−1k-1 pairwise coprime moduli. Given pairwise coprime m1,…,mkm_1,\dots,m_k and targets a1,…,aka_1,\dots,a_k, apply the inductive hypothesis to the first k−1k-1 congruences: there is y0y_0 such that

x≡a1(modm1),…,x≡ak−1(modmk−1)  ⟺  x≡y0(modN),N:=m1m2⋯mk−1.x \equiv a_1 \pmod{m_1}, \dots, x \equiv a_{k-1} \pmod{m_{k-1}} \iff x \equiv y_0 \pmod{N}, \qquad N := m_1 m_2 \cdots m_{k-1}.

We must show NN and mkm_k are coprime, so that we may apply the Lemma to combine x≡y0(modN)x \equiv y_0 \pmod N with x≡ak(modmk)x \equiv a_k \pmod{m_k}. Claim: gcd⁡(N,mk)=1\gcd(N, m_k) = 1. Suppose a prime pp divided both NN and mkm_k. Since p∣N=m1⋯mk−1p \mid N = m_1 \cdots m_{k-1}, Euclid's lemma (a prime dividing a product divides one of the factors) implies p∣mip \mid m_i for some i≤k−1i \le k-1. But then pp divides both mim_i and mkm_k, contradicting the hypothesis gcd⁡(mi,mk)=1\gcd(m_i, m_k) = 1 (pairwise coprimality, i≠ki \neq k). Hence no prime divides both NN and mkm_k, so gcd⁡(N,mk)=1\gcd(N,m_k)=1, proving the claim. Now apply the Lemma to the coprime pair (N,mk)(N, m_k) with target residues y0  Ny_0 \bmod N and ak  mka_k \bmod m_k: there exists x0x_0 with

x≡y0(modN)andx≡ak(modmk)  ⟺  x≡x0(modNmk).x \equiv y_0 \pmod{N} \quad\text{and}\quad x \equiv a_k \pmod{m_k} \iff x \equiv x_0 \pmod{Nm_k}.

Since Nmk=m1m2⋯mk=MNm_k = m_1 m_2 \cdots m_k = M, and since "x≡y0(modN)x \equiv y_0 \pmod N" is equivalent to the first k−1k-1 original congruences, we conclude

x≡a1(modm1),…,x≡ak(modmk)  ⟺  x≡x0(modM).x \equiv a_1 \pmod{m_1}, \dots, x \equiv a_k \pmod{m_k} \iff x \equiv x_0 \pmod{M}.

This is exactly the statement of the theorem for kk moduli, completing the induction. ■\blacksquare

Remark on rigor and non-circularity. The proof uses only: (1) the Euclidean algorithm / Bézout's identity for two coprime integers, and (2) Euclid's lemma about primes dividing products — both logically prior results, part of the foundations of Linear Congruences and elementary divisibility theory, not derived from the CRT itself. No step assumes the conclusion.

∎
CorollaryRing isomorphism form

Let m,nm,n be positive integers with gcd⁡(m,n)=1\gcd(m,n) = 1. Then the map

φ:Z/mnZ⟶Z/mZ×Z/nZ,φ(x  mn)=(x  m, x  n)\varphi : \mathbb{Z}/mn\mathbb{Z} \longrightarrow \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}, \qquad \varphi(x \bmod mn) = (x \bmod m,\ x \bmod n)

is a well-defined bijection, and in fact a ring isomorphism (it respects addition and multiplication). More generally, for pairwise coprime m1,…,mkm_1,\dots,m_k with M=m1⋯mkM = m_1\cdots m_k,

Z/MZ  ≅  Z/m1Z×⋯×Z/mkZ.\mathbb{Z}/M\mathbb{Z} \;\cong\; \mathbb{Z}/m_1\mathbb{Z} \times \cdots \times \mathbb{Z}/m_k\mathbb{Z}.
Proof

Well-defined: if x≡x′(modmn)x \equiv x' \pmod {mn} then certainly x≡x′(modm)x \equiv x' \pmod m and x≡x′(modn)x \equiv x' \pmod n (since m,nm,n divide mnmn), so φ\varphi does not depend on the chosen representative xx.

Injective: if φ(x  mn)=φ(x′  mn)\varphi(x \bmod mn) = \varphi(x' \bmod mn), then x≡x′(modm)x \equiv x' \pmod m and x≡x′(modn)x \equiv x' \pmod n. This is precisely the hypothesis in the uniqueness half of the two-modulus Lemma applied with a=b=a=b= common residue; the argument there (using gcd⁡(m,n)=1\gcd(m,n)=1 and Euclid's lemma) shows x≡x′(modmn)x \equiv x' \pmod{mn}. Hence φ\varphi is injective.

Surjective: given any target pair (a  m,b  n)(a \bmod m, b \bmod n), the Lemma produces x0x_0 with φ(x0  mn)=(a  m,b  n)\varphi(x_0 \bmod mn) = (a\bmod m, b\bmod n). So φ\varphi is surjective. Since Z/mnZ\mathbb{Z}/mn\mathbb{Z} and Z/mZ×Z/nZ\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z} both have exactly mnmn elements (the codomain has m⋅nm\cdot n pairs), an injective map between finite sets of equal size is automatically a bijection — this also gives an independent confirmation of surjectivity.

Ring homomorphism: for x,y∈Zx,y \in \mathbb{Z},

φ((x+y)  mn)=((x+y)  m, (x+y)  n)=(x  m+y  m, x  n+y  n)=φ(x)+φ(y),\varphi((x+y)\bmod mn) = ((x+y)\bmod m,\ (x+y)\bmod n) = (x\bmod m + y \bmod m,\ x\bmod n + y\bmod n) = \varphi(x)+\varphi(y),

using that reduction mod mm (resp. nn) is a ring homomorphism from Z\mathbb{Z}, and similarly

φ((xy)  mn)=(xy  m, xy  n)=(x  m)(y  m), (x  n)(y  n))=φ(x)φ(y).\varphi((xy)\bmod mn) = (xy \bmod m,\ xy\bmod n) = (x\bmod m)(y\bmod m),\ (x\bmod n)(y\bmod n)) = \varphi(x)\varphi(y).

Thus φ\varphi is a bijective ring homomorphism, i.e. a ring isomorphism. The kk-modulus statement follows by the same induction used in the theorem's proof, combining one modulus at a time and using that a composite of ring isomorphisms (or an isomorphism onto an iterated product identified with the full product) is again a ring isomorphism. ■\blacksquare

∎

Worked examples

Example 1 — three moduli, asymmetric remainders. Solve simultaneously:

x≡4(mod5),x≡7(mod9),x≡3(mod11).x \equiv 4 \pmod 5, \qquad x \equiv 7 \pmod 9, \qquad x \equiv 3 \pmod{11}.

Check pairwise coprimality: gcd⁡(5,9)=1\gcd(5,9)=1, gcd⁡(5,11)=1\gcd(5,11)=1, gcd⁡(9,11)=1\gcd(9,11)=1. Good, the theorem applies, and M=5⋅9⋅11=495M = 5\cdot 9\cdot 11 = 495. Step 1 (combine first two moduli). We want y0y_0 with y0≡4(mod5)y_0 \equiv 4 \pmod 5, y0≡7(mod9)y_0 \equiv 7 \pmod 9. Bézout for (5,9)(5,9): since 2⋅5−1⋅9=12\cdot 5 - 1\cdot 9 = 1, we have u=2,v=−1u=2, v=-1 with u⋅5+v⋅9=1u\cdot5 + v\cdot 9 = 1. Using the formula y0=a vn+b umy_0 = a\,vn + b\,um with a=4,m=5,b=7,n=9,u=2,v=−1a=4,m=5,b=7,n=9,u=2,v=-1:

y0=4⋅(−1)⋅9+7⋅2⋅5=−36+70=34.y_0 = 4\cdot(-1)\cdot 9 + 7\cdot 2 \cdot 5 = -36 + 70 = 34.

Check: 34=6⋅5+4≡4(mod5)34 = 6\cdot5+4 \equiv 4\pmod5 ✓, and 34=3⋅9+7≡7(mod9)34 = 3\cdot9+7\equiv7\pmod9 ✓. So x≡34(mod45)x \equiv 34 \pmod{45} (since N=5⋅9=45N=5\cdot9=45) captures the first two congruences. Step 2 (combine with the third modulus). Now solve x≡34(mod45)x \equiv 34 \pmod{45}, x≡3(mod11)x \equiv 3 \pmod{11}. Bézout for (45,11)(45,11): gcd⁡(45,11)=1\gcd(45,11)=1. We find u,vu,v with 45u+11v=145u + 11v = 1. Using the Euclidean algorithm: 45=4⋅11+145 = 4\cdot11 + 1, so 1=45−4⋅111 = 45 - 4\cdot 11, giving u=1u=1, v=−4v=-4. Apply the formula with a=34,m=45,b=3,n=11,u=1,v=−4a=34, m=45, b=3, n=11, u=1, v=-4:

x0=34⋅(−4)⋅11+3⋅1⋅45=−1496+135=−1361.x_0 = 34\cdot(-4)\cdot 11 + 3\cdot 1 \cdot 45 = -1496 + 135 = -1361.

Reduce modulo 495495: −1361+3⋅495=−1361+1485=124-1361 + 3\cdot 495 = -1361+1485 = 124. Verification of x0=124x_0 = 124: 124=24⋅5+4124 = 24\cdot5+4, so 124≡4(mod5)124\equiv 4\pmod5 ✓. 124=13⋅9+7124 = 13\cdot9+7, so 124≡7(mod9)124\equiv7\pmod9 ✓. 124=11⋅11+3124=11\cdot11+3, so 124≡3(mod11)124\equiv3\pmod{11} ✓. So the full solution set is x≡124(mod495)x \equiv 124 \pmod{495}, and every such xx (e.g. 124,619,1114,…124, 619, 1114, \dots and −371,…-371,\dots) satisfies all three original congruences, while no other residue class mod 495495 does, by the uniqueness half of the theorem.

Example 2 — ring-isomorphism computation with m=8m=8, n=15n=15 (coprime, non-prime moduli). Here gcd⁡(8,15)=1\gcd(8,15)=1, M=120M=120. Consider the element 17  120∈Z/120Z17 \bmod 120 \in \mathbb{Z}/120\mathbb{Z}. Under the isomorphism φ:Z/120Z→Z/8Z×Z/15Z\varphi: \mathbb{Z}/120\mathbb{Z}\to\mathbb{Z}/8\mathbb{Z}\times\mathbb{Z}/15\mathbb{Z} we get

φ(17)=(17  8, 17  15)=(1,2).\varphi(17) = (17 \bmod 8,\ 17\bmod 15) = (1, 2).

Now let's verify the homomorphism property with a second element, 53  12053 \bmod 120:

φ(53)=(53  8, 53  15)=(5,8).\varphi(53) = (53 \bmod 8,\ 53 \bmod 15) = (5, 8).

Compute the product 17⋅53=90117\cdot 53 = 901 in Z/120Z\mathbb{Z}/120\mathbb{Z}: 901=7⋅120+61901 = 7\cdot120+61, so 17⋅53≡61(mod120)17\cdot53 \equiv 61 \pmod{120}, and

φ(61)=(61  8, 61  15)=(5,1).\varphi(61) = (61\bmod 8,\ 61\bmod15) = (5, 1).

On the other side, the product of the images should be φ(17)⋅φ(53)=(1,2)⋅(5,8)=(1⋅5  8, 2⋅8  15)=(5,16  15)=(5,1)\varphi(17)\cdot\varphi(53) = (1,2)\cdot(5,8) = (1\cdot5 \bmod 8,\ 2\cdot 8\bmod 15) = (5, 16\bmod15) = (5,1). Both sides agree: (5,1)=(5,1)(5,1) = (5,1), confirming φ(17⋅53)=φ(17)φ(53)\varphi(17\cdot53) = \varphi(17)\varphi(53) concretely, exactly as the ring-homomorphism corollary predicts. This illustrates the practical payoff: multiplying two numbers mod 120120 can be done by multiplying their reductions mod 88 and mod 1515 independently — a technique underlying fast modular arithmetic in cryptographic implementations.

CounterexampleDropping pairwise coprimality

Consider moduli m=4m=4 and n=6n=6, which are not coprime since gcd⁡(4,6)=2\gcd(4,6)=2. Take the system

x≡1(mod4),x≡2(mod6).x \equiv 1 \pmod 4, \qquad x \equiv 2 \pmod 6.

Reducing both congruences modulo gcd⁡(4,6)=2\gcd(4,6)=2: the first forces x≡1(mod2)x \equiv 1 \pmod 2 (odd xx), while the second forces x≡0(mod2)x \equiv 0 \pmod 2 (even xx), a direct contradiction. So no solution exists at all, even though each congruence individually is perfectly solvable. Contrast with a compatible but still non-coprime example: x≡2(mod4)x\equiv 2\pmod4 and x≡2(mod6)x\equiv 2\pmod6. Here x=2x=2 works, and also x=14,26,…x=14, 26,\dots; one checks the full solution set is x≡2(mod12)x\equiv 2\pmod{12}. But note 12≠4⋅6=2412 \neq 4\cdot 6 = 24: the modulus of the solution class is lcm(4,6)=12\mathrm{lcm}(4,6)=12, not the naive product 2424. So even when a solution exists, the clean "unique modulo M=mnM=mn" conclusion of the theorem fails — the true period is lcm(m,n)\mathrm{lcm}(m,n), which is smaller than mnmn precisely because gcd⁡(m,n)=2>1\gcd(m,n) = 2 > 1. This shows pairwise coprimality is not a cosmetic simplification: without it, (a) existence can fail outright, and (b) even when existence holds, uniqueness only holds modulo lcm(m,n)\mathrm{lcm}(m,n), so the specific numerical conclusion "unique mod mnmn" of the theorem is false in general.

Scope, edge cases & common traps

SituationWhat happens
Moduli pairwise coprimeTheorem applies fully: solution exists, unique mod M=∏miM=\prod m_i
Moduli share a common factor, congruences compatibleSolution exists but is unique only modulo lcm(mi)\mathrm{lcm}(m_i), which is strictly less than ∏mi\prod m_i
Moduli share a common factor, congruences incompatibleNo solution exists at all
k=1k=1Trivial; the "system" is a single congruence, already solved by definition
Some aia_i negative or ≥mi\ge m_iNo issue: congruences depend only on residues, reduce first if convenient

The mathematician behind it

Origins · 1 minSun Zi and how this was discovered
SZ
Sun Zi
circa 3rd–5th century CE · Chinese mathematics

Sun Zi (孙子), author of the Sunzi Suanjing ("Sun Zi's Mathematical Manual"), is credited with the earliest known statement and solution of a simultaneous congruence problem — the "three, five, seven" puzzle asking for a number leaving remainders 2,3,22, 3, 2 upon division by 3,5,73, 5, 7. Little is known of his life; even his exact dates are debated, placed anywhere from the 3rd to the 5th century CE. His work was preserved and expanded over centuries by Chinese mathematicians, culminating in a fully general method — Qin Jiushao's "Da Yan" (大衍) rule of 1247 — for solving such systems with arbitrary pairwise coprime moduli, essentially the constructive algorithm proved above.

History
- 3rd–5th century: Sun Zi's manual poses and solves the "remainder problem" for three specific small moduli.
- 1247: Qin Jiushao, in the Shùshū Jiǔzhāng ("Mathematical Treatise in Nine Sections"), gives a systematic general algorithm for arbitrary pairwise coprime moduli.
- 1801: Carl Friedrich Gauss, in Disquisitiones Arithmeticae, formalizes congruence notation and rederives the result within the modern theory of congruences.
- 19th–20th century: The theorem is recognized as a special case of ring-theoretic decomposition, generalized to arbitrary commutative rings via comaximal ideals.
- 20th–21st century: The theorem becomes foundational in computational number theory, coding theory, and cryptographic engineering.
Does the Chinese Remainder Theorem require the moduli to be prime?

No. The theorem only requires the moduli to be pairwise coprime, meaning any two distinct moduli share no common factor greater than 11. They need not be prime individually; for instance 88 and 1515 are coprime despite neither being prime. The proof relies only on Bézout's identity for coprime integers and Euclid's lemma, both of which hold regardless of whether the numbers involved are prime. Primality is a red herring here — what matters is the pairwise gcd condition. This is worth remembering because many students conflate "coprime" with "prime," but a modulus like 9=329=3^2 can happily be one of the pairwise coprime moduli in a CRT system, as in the worked example with moduli 5,9,115, 9, 11.

What happens if the moduli are not pairwise coprime but the system happens to be consistent?

A solution can still exist, but the clean statement "unique modulo the product MM" no longer holds. Instead, the correct modulus for uniqueness becomes lcm(m1,…,mk)\mathrm{lcm}(m_1,\dots,m_k), which is smaller than ∏mi\prod m_i whenever the moduli share common factors. Consistency itself requires checking that whenever two moduli share a common factor dd, the corresponding remainders agree modulo dd; if they don't, there is no solution. This more general statement (sometimes called the generalized CRT) is provable using the same ideas but needs care with gcd/lcm bookkeeping instead of a straightforward product.

Why is the ring-isomorphism formulation more powerful than the "just find x" formulation?

The elementary formulation answers a single existence-and-uniqueness question, which is enough for solving specific numerical systems. The ring-isomorphism formulation tells you that arithmetic itself — addition and multiplication — transports correctly between Z/mnZ\mathbb{Z}/mn\mathbb{Z} and the product Z/mZ×Z/nZ\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}. This means entire computations, not just single solutions, can be split apart and done independently modulo each factor, then recombined. That structural insight is what powers applications like CRT-accelerated RSA decryption and residue number system arithmetic, where the goal is fast repeated computation, not a one-off congruence solve.

Is the CRT algorithm actually efficient, or just a theoretical existence proof?

It is genuinely constructive and efficient. The proof builds x0x_0 directly from Bézout coefficients obtained via the Euclidean algorithm, which runs in time polynomial in the number of digits of the moduli. Combining kk congruences pairwise, as in the induction, takes k−1k-1 applications of the two-modulus step, each essentially one Euclidean algorithm run. This is why the CRT is used as a real computational tool, not merely cited as an abstract existence theorem — it is as constructive as solving a single linear congruence.

How does the CRT relate to Euler's totient function?

Via the ring isomorphism Z/mnZ≅Z/mZ×Z/nZ\mathbb{Z}/mn\mathbb{Z}\cong\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z} for coprime m,nm,n: an element is a unit in a product ring exactly when each coordinate is a unit in its own factor ring. Counting units on both sides gives φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m)\varphi(n), the multiplicativity of the totient function. This is one of the cleanest structural proofs of that multiplicativity, and it is a direct foreshadowing of how the CRT is used to analyze Z/nZ\mathbb{Z}/n\mathbb{Z} for general nn by breaking nn into prime power factors.

Can the Chinese Remainder Theorem be generalized beyond the integers?

Yes. The same proof strategy works in any principal ideal domain, and more generally in any commutative ring for comaximal ideals I,JI,J (meaning I+JI+J equals the whole ring), giving R/(I∩J)≅R/I×R/JR/(I\cap J) \cong R/I \times R/J. This is the natural habitat of the theorem in abstract algebra and is used, for example, in polynomial interpolation (viewing polynomials modulo distinct linear factors (x−ai)(x-a_i) as comaximal ideals) and in algebraic number theory when working with ideals in rings of integers.

Why does the proof need induction rather than handling all k moduli at once?

Because the core combinatorial fact — that two coprime numbers admit a Bézout combination summing to 11 — is inherently a two-number statement; there is no direct analogue of "Bézout's identity" simultaneously for k>2k>2 numbers that isn't itself built from repeated pairwise combination. The induction lets us reduce the kk-modulus problem to a sequence of two-modulus problems, each justified by the coprimality of the running product N=m1⋯mk−1N=m_1\cdots m_{k-1} with the next modulus mkm_k — a fact itself proved using Euclid's lemma. This keeps the whole argument grounded in elementary, previously established facts with no circular dependence on the theorem being proved.

Before this

Where this leads