The Chinese Remainder Theorem

Suppose you know a number's remainder mod 3 and mod 5. Can you always reconstruct the number mod 15? This ancient question was first posed by Chinese astronomers tracking calendars. It turns out to be a shadow of a deep structural fact about rings. The Chinese Remainder Theorem says that solving simultaneous congruences is not a numerical trick. Instead, it is a manifestation of a canonical isomorphism. This isomorphism links a quotient ring and a product of simpler quotient rings. It holds whenever the ideals involved are "comaximal" — spread out enough in the ring to not interfere with each other. The theorem matters because it converts a single complicated quotient ring into a product of smaller, often much simpler, pieces. Products of rings are easy to understand: an element is just a tuple. Arithmetic happens coordinate-by-coordinate. When a ring R/IR/I decomposes as R/I1×⋯×R/InR/I_1 \times \cdots \times R/I_n, questions about units, idempotents, nilpotents, and zero-divisors in R/IR/I reduce to the same questions in each factor. This is frequently trivial. This is why CRT is a workhorse behind fast integer arithmetic, structure theorems for finite abelian groups, decomposition of finite-dimensional algebras, and the factorization of polynomials modulo primes. The big picture is that ring quotients "see" a ring only through the lens of one ideal at a time. CRT tells you exactly when several such lenses can be combined losslessly into one panoramic view. The condition for this combination to work — comaximality, meaning I+J=RI + J = R — is a purely ideal-theoretic condition. It generalizes the arithmetic condition gcd⁡(m,n)=1\gcd(m,n)=1. This shift from "numbers being coprime" to "ideals being comaximal" is exactly the kind of abstraction that lets the same theorem apply to Z\mathbb{Z}, to polynomial rings, and to arbitrary commutative rings with identity. This article states and proves the Chinese Remainder Theorem in its general ring-theoretic form. It covers both two ideals and finitely many pairwise comaximal ideals. It builds the isomorphism explicitly using the Isomorphism Theorems for Rings and the algebra of ideal Operations on Ideals: Sum, Product, Intersection. Two fully worked examples show the theorem in action, in Z\mathbb{Z} and in a polynomial ring. A counterexample shows exactly what fails without the comaximality hypothesis.

Key takeaways
  • CRT expresses R/(I∩J)R/(I \cap J) as R/I×R/JR/I \times R/J precisely when I+J=RI + J = R (the ideals are comaximal).
  • The isomorphism is induced by the canonical map r↦(r+I, r+J)r \mapsto (r+I,\, r+J), using the First Isomorphism Theorem.
  • Comaximality forces I∩J=IJI \cap J = IJ, so the theorem can equivalently use the product ideal.
  • The general nn-ideal version needs pairwise comaximality, not just joint comaximality of the whole family.
  • In Z\mathbb{Z}, comaximal ideals are exactly (m)(m) and (n)(n) with gcd⁡(m,n)=1\gcd(m,n)=1, recovering classical CRT.
  • Key idea: solving simultaneous congruences is the same as building an element of a product ring one coordinate at a time.

Where this lives today

CRT underlies fast modular arithmetic in computer algebra systems and cryptographic implementations: large integer computations (e.g. in RSA decryption) are sped up by splitting a computation modulo a big number N=pqN=pq into independent computations modulo pp and modulo qq, then recombining via the explicit reconstruction formula from the proof. In algebraic number theory, CRT explains how a number ring modulo an ideal decomposes according to the ideal's prime factorization, feeding directly into the theory of splitting of primes. In the structure theory of finite abelian groups, CRT (applied to Z/nZ\mathbb{Z}/n\mathbb{Z} with nn factored into prime powers) proves Z/nZ≅∏pZ/papZ\mathbb{Z}/n\mathbb{Z} \cong \prod_p \mathbb{Z}/p^{a_p}\mathbb{Z}, a key ingredient in the classification of finite abelian groups. In polynomial interpolation and coding theory (Reed–Solomon codes), the polynomial-ring instance of CRT is exactly the statement underlying Lagrange interpolation, as seen in the second worked example. In algebraic geometry, CRT expresses that a scheme supported on several disjoint closed points behaves like a product, foreshadowing sheaf-theoretic gluing constructions.

Ask the tutor: How does the Chinese Remainder Theorem generalize to decomposing modules over a PID into their prime-power components?

DefinitionComaximal ideals and the CRT isomorphism

Let RR be a ring with identity (not necessarily commutative unless stated). Two ideals I,J⊴RI, J \trianglelefteq R are comaximal (or coprime) if

I+J=R.I + J = R.

Equivalently, there exist a∈Ia \in I and b∈Jb \in J with a+b=1a + b = 1. More generally, ideals I1,…,In⊴RI_1, \dots, I_n \trianglelefteq R are pairwise comaximal if Ik+Iℓ=RI_k + I_\ell = R for every pair k≠ℓk \neq \ell. Given ideals I,JI, J, define the map

φ:R⟶R/I×R/J,φ(r)=(r+I, r+J).\varphi : R \longrightarrow R/I \times R/J, \qquad \varphi(r) = (r + I,\ r + J).

This is a ring homomorphism (verified below), and the Chinese Remainder Theorem identifies its kernel and, when I,JI,J are comaximal, shows φ\varphi is surjective, yielding a ring isomorphism

R/(I∩J)  ≅  R/I×R/J.R/(I \cap J) \;\cong\; R/I \times R/J.

Intuition

Think of an element r∈Rr \in R as a point, and each ideal II as defining a "measurement" of rr: the coset r+Ir + I tells you where rr sits relative to II, forgetting everything II itself contains. Two ideals give two independent measurements. The question CRT answers is: given two target measurements (a coset of II and a coset of JJ), is there always a single element realizing both simultaneously, and if so, how much freedom do we have in choosing it? Comaximality, I+J=RI + J = R, is precisely the condition guaranteeing no obstruction: it says you can write 1=a+b1 = a + b with a∈Ia\in I, b∈Jb \in J, and this decomposition of unity is the raw material used to build an element realizing any prescribed pair of target cosets. The uniqueness (up to the freedom of I∩JI \cap J) is measured by the kernel of the comparison map φ\varphi, which is exactly I∩JI \cap J. So the whole theorem is the statement that the "measurement map" into the product is exactly as surjective and exactly as far from injective as comaximality permits. The picture below shows the classical case R=ZR = \mathbb{Z}, I=(3)I = (3), J=(5)J = (5). The residues mod 3 and mod 5 are shown on two separate number-line "clocks"; CRT says every pair of residues corresponds to a unique residue mod 15.

Figure
The residue pairs mod 3 and mod 5 correspond bijectively to residues mod 15
mod 3 clock (I = (3)) 0 1 2 mod 5 clock (J = (5)) 0 1 2 3 4 r = 8: 8 mod 3 = 2, 8 mod 5 = 3 ⟶ unique r mod 15 = 8

Central theorem

TheoremChinese Remainder Theorem, two-ideal form

Let RR be a ring with identity 1≠01 \neq 0, and let I,J⊴RI, J \trianglelefteq R be (two-sided) ideals. Define

φ:R→R/I×R/J,φ(r)=(r+I, r+J).\varphi : R \to R/I \times R/J, \qquad \varphi(r) = (r+I,\ r+J).

Then: 1. φ\varphi is a ring homomorphism with ker⁡φ=I∩J\ker \varphi = I \cap J. 2. If II and JJ are comaximal (i.e. I+J=RI + J = R), then φ\varphi is surjective, and consequently

R/(I∩J)  ≅  R/I×R/JR/(I \cap J) \;\cong\; R/I \times R/J

as rings, via the induced map φˉ(r+I∩J)=(r+I, r+J)\bar\varphi(r + I\cap J) = (r+I,\ r+J). 3. If RR is commutative and I,JI, J are comaximal, then I∩J=IJI \cap J = IJ, so equivalently

R/IJ  ≅  R/I×R/J.R/IJ \;\cong\; R/I \times R/J.
LemmaIdempotent witnesses

Under the hypotheses of part 2 above, there exist e∈Ie \in I, f∈Jf \in J with e+f=1e + f = 1. The elements e+I∩J=(0,1)e + I \cap J = (0, 1)-preimage and f+I∩Jf + I \cap J act as the "coordinate idempotents" of the decomposition: φˉ(f)=(1+I, 0+J)\bar\varphi(f) = (1+I,\, 0+J) and φˉ(e)=(0+I, 1+J)\bar\varphi(e) = (0+I,\, 1+J).

Proof

We prove the theorem's three parts in order, using direct verification and the First Isomorphism Theorem. The proof technique throughout is direct construction: we build the required elements and maps explicitly rather than arguing abstractly.

Part 1: φ\varphi is a homomorphism with kernel I∩JI \cap J. The projections πI:R→R/I\pi_I : R \to R/I, r↦r+Ir \mapsto r + I, and πJ:R→R/J\pi_J : R \to R/J, r↦r+Jr \mapsto r + J, are each ring homomorphisms (the canonical quotient maps). The product ring R/I×R/JR/I \times R/J has componentwise operations:

(a1,b1)+(a2,b2)=(a1+a2, b1+b2),(a1,b1)⋅(a2,b2)=(a1a2, b1b2).(a_1,b_1) + (a_2,b_2) = (a_1+a_2,\ b_1+b_2), \qquad (a_1,b_1)\cdot(a_2,b_2) = (a_1 a_2,\ b_1 b_2).

The map φ=(πI,πJ)\varphi = (\pi_I, \pi_J), i.e. φ(r)=(πI(r),πJ(r))\varphi(r) = (\pi_I(r), \pi_J(r)), is a ring homomorphism because each coordinate is: for r,s∈Rr,s \in R,

φ(r+s)=(πI(r+s),πJ(r+s))=(πI(r)+πI(s), πJ(r)+πJ(s))=φ(r)+φ(s),\varphi(r+s) = (\pi_I(r+s), \pi_J(r+s)) = (\pi_I(r)+\pi_I(s),\ \pi_J(r)+\pi_J(s)) = \varphi(r)+\varphi(s),

and identically for multiplication, since πI,πJ\pi_I, \pi_J each preserve products. Also φ(1)=(1+I,1+J)=(1,1)\varphi(1) = (1+I, 1+J) = (1,1), the multiplicative identity of R/I×R/JR/I \times R/J, so φ\varphi is unital. Now compute the kernel. By definition,

r∈ker⁡φ  ⟺  (r+I, r+J)=(0+I, 0+J)  ⟺  r∈I and r∈J  ⟺  r∈I∩J.r \in \ker \varphi \iff (r+I,\ r+J) = (0+I,\ 0+J) \iff r \in I \text{ and } r \in J \iff r \in I \cap J.

Hence ker⁡φ=I∩J\ker\varphi = I \cap J. Note this holds unconditionally — no comaximality is used yet — and I∩JI \cap J is indeed an ideal of RR (an intersection of ideals is always an ideal, as established in Operations on Ideals: Sum, Product, Intersection), consistent with the kernel of a ring homomorphism always being an ideal.

Part 2: comaximality implies surjectivity, and the induced isomorphism. Assume I+J=RI + J = R. Since 1∈R=I+J1 \in R = I + J, there exist e∈Ie \in I and f∈Jf \in J with

e+f=1.e + f = 1.

We claim φ(f)=(1+I, 0+J)\varphi(f) = (1+I,\ 0+J) and φ(e)=(0+I, 1+J)\varphi(e) = (0+I,\ 1+J). Indeed, since e∈Ie \in I, we have e+I=0+Ie + I = 0 + I, and from e+f=1e + f = 1 we get f=1−ef = 1 - e, so f+I=1−e+I=1+If + I = 1 - e + I = 1 + I (using e∈Ie \in I again, so −e∈I-e \in I). Thus φ(f)=(1+I, f+J)\varphi(f) = (1+I,\ f+J). But also f∈Jf \in J, so f+J=0+Jf + J = 0 + J. Hence φ(f)=(1+I, 0+J)\varphi(f) = (1+I,\ 0+J) as claimed. Symmetrically, since e=1−fe = 1 - f and f∈Jf \in J, we get e+J=1+Je + J = 1 + J; and since e∈Ie \in I, e+I=0+Ie + I = 0+I. So φ(e)=(0+I, 1+J)\varphi(e) = (0+I,\ 1+J). Now take an arbitrary target (a+I, b+J)∈R/I×R/J(a+I,\ b+J) \in R/I \times R/J with a,b∈Ra,b \in R. Set

r:=af+be.r := a f + b e.

We compute φ(r)\varphi(r) coordinate by coordinate using that φ\varphi is a ring homomorphism (so it respects the linear combination):

φ(r)=a φ(f)+b φ(e)=a (1+I, 0+J)+b (0+I, 1+J).\varphi(r) = a\,\varphi(f) + b\,\varphi(e) = a\,(1+I,\ 0+J) + b\,(0+I,\ 1+J).

Here we are using the RR-module-like action of RR on R/I×R/JR/I \times R/J coordinatewise, i.e. a⋅(1+I, 0+J)=(a+I, 0+J)a\cdot(1+I,\,0+J) = (a+I,\, 0+J) since a⋅1=aa\cdot 1 = a and a⋅0=0a \cdot 0 = 0 in each quotient ring; likewise for b⋅(0+I, 1+J)=(0+I, b+J)b\cdot(0+I,\,1+J) = (0+I,\,b+J). Adding these:

φ(r)=(a+I, 0+J)+(0+I, b+J)=(a+I, b+J).\varphi(r) = (a+I,\ 0+J) + (0+I,\ b+J) = (a+I,\ b+J).

This is precisely the target pair. Since (a+I,b+J)(a+I, b+J) was arbitrary, φ\varphi is surjective. We have now shown φ:R→R/I×R/J\varphi : R \to R/I \times R/J is a surjective ring homomorphism with ker⁡φ=I∩J\ker \varphi = I \cap J (Part 1, which required no extra hypothesis). By the First Isomorphism Theorem for rings, applied to φ\varphi, there is a ring isomorphism

φˉ:R/(I∩J)→ ∼ R/I×R/J,φˉ(r+I∩J)=φ(r)=(r+I, r+J),\bar\varphi : R/(I \cap J) \xrightarrow{\ \sim\ } R/I \times R/J, \qquad \bar\varphi(r + I \cap J) = \varphi(r) = (r+I,\ r+J),

which is well-defined precisely because I∩J=ker⁡φI \cap J = \ker\varphi, and it is a bijective ring homomorphism by the First Isomorphism Theorem's conclusion. This proves Part 2.

Part 3: commutativity and comaximality give I∩J=IJI \cap J = IJ. Assume in addition RR is commutative. Recall IJIJ denotes the ideal generated by all products xyxy with x∈Ix \in I, y∈Jy \in J; equivalently (since RR is commutative) IJIJ is the set of finite sums ∑kxkyk\sum_k x_k y_k with xk∈I,yk∈Jx_k \in I, y_k \in J, as developed in Operations on Ideals: Sum, Product, Intersection. (IJ⊆I∩JIJ \subseteq I \cap J, always true, no hypothesis needed.) For x∈Ix \in I, y∈Jy \in J, we have xy∈Ixy \in I because II is an ideal and y∈Ry \in R (absorption), and xy∈Jxy \in J symmetrically. So every generator of IJIJ lies in I∩JI \cap J, and since I∩JI \cap J is an ideal (closed under addition), all finite sums of such generators lie in I∩JI \cap J. Hence IJ⊆I∩JIJ \subseteq I \cap J. (I∩J⊆IJI \cap J \subseteq IJ, using comaximality). Let z∈I∩Jz \in I \cap J. Using the same e∈Ie \in I, f∈Jf \in J with e+f=1e + f = 1 from Part 2, multiply by zz:

z=z⋅1=z(e+f)=ze+zf.z = z\cdot 1 = z(e+f) = ze + zf.

Now z∈Jz \in J and e∈Ie \in I, so ze∈JI=IJze \in JI = IJ (using commutativity of RR to identify JIJI with IJIJ as ideals — both equal the ideal generated by all products of an element of II and one of JJ). Also z∈Iz \in I and f∈Jf \in J, so zf∈IJzf \in IJ. Since IJIJ is an ideal (in particular closed under addition), z=ze+zf∈IJz = ze + zf \in IJ. Hence I∩J⊆IJI \cap J \subseteq IJ. Combining both inclusions, I∩J=IJI \cap J = IJ. Substituting into Part 2's conclusion gives

R/IJ  ≅  R/I×R/J.R/IJ \;\cong\; R/I \times R/J.

This completes the proof of all three parts. ■\blacksquare

∎
CorollaryChinese Remainder Theorem, nn-ideal form

Let RR be a ring with identity, and let I1,…,In⊴RI_1, \dots, I_n \trianglelefteq R be pairwise comaximal ideals (that is, Ik+Iℓ=RI_k + I_\ell = R for all k≠ℓk \neq \ell). Then

R/⋂k=1nIk  ≅  R/I1×R/I2×⋯×R/In,R \Big/ \bigcap_{k=1}^n I_k \;\cong\; R/I_1 \times R/I_2 \times \cdots \times R/I_n,

via r+⋂kIk↦(r+I1,…,r+In)r + \bigcap_k I_k \mapsto (r+I_1, \dots, r+I_n). If moreover RR is commutative, then ⋂kIk=I1I2⋯In\bigcap_k I_k = I_1 I_2 \cdots I_n, so equivalently R/(I1⋯In)≅∏kR/IkR/(I_1\cdots I_n) \cong \prod_k R/I_k.

Proof

We argue by induction on nn, with the two-ideal theorem above as the base case n=2n = 2. Base case n=2n=2: this is exactly the theorem just proved. Inductive step: Suppose n≥3n \geq 3 and the result holds for any n−1n-1 pairwise comaximal ideals in any ring with identity. Given pairwise comaximal I1,…,In⊴RI_1,\dots,I_n \trianglelefteq R, set K=I2∩⋯∩InK = I_2 \cap \cdots \cap I_n. By the inductive hypothesis applied to I2,…,InI_2,\dots,I_n (pairwise comaximal by assumption),

R/K  ≅  R/I2×⋯×R/In.(∗)R/K \;\cong\; R/I_2 \times \cdots \times R/I_n. \tag{$\ast$}

We claim I1I_1 and KK are comaximal, i.e. I1+K=RI_1 + K = R. Since I1+Ik=RI_1 + I_k = R for each k=2,…,nk = 2,\dots,n, for each such kk we may write 1=ak+bk1 = a_k + b_k with ak∈I1a_k \in I_1, bk∈Ikb_k \in I_k. Consider the product

∏k=2n(ak+bk)=∏k=2n1=1.\prod_{k=2}^{n} (a_k + b_k) = \prod_{k=2}^n 1 = 1.

Expand this product formally (in the possibly noncommutative ring RR, keeping the factors in order k=2,…,nk=2,\dots,n as written, which is legitimate since we are just expanding a formal product of sums using distributivity). Every term in the expansion is a product of n−1n-1 factors, each factor being either some ak∈I1a_k \in I_1 or some bk∈Ikb_k \in I_k. The single term in which every factor is chosen to be bkb_k equals b2b3⋯bnb_2 b_3 \cdots b_n, which lies in I2∩⋯∩In=KI_2 \cap \cdots \cap I_n = K — indeed b2b3⋯bn∈Kb_2 b_3\cdots b_n \in K because, for each fixed j∈{2,…,n}j \in \{2,\dots,n\}, the factor bj∈Ijb_j \in I_j and IjI_j is a two-sided ideal, so absorbing the remaining factors (elements of RR) on either side keeps the product inside IjI_j; this holds for every jj, so the product lies in every IjI_j, hence in their intersection KK. Every other term in the expansion has at least one factor equal to some ak∈I1a_k \in I_1; since I1I_1 is a two-sided ideal, absorbing the remaining factors (which lie in RR) on either side of aka_k keeps that whole term inside I1I_1. Hence every other term lies in I1I_1. Grouping the expansion as (the all-bb term) ++ (sum of all other terms), we get

1=b2b3⋯bn⏟∈ K+(sum of remaining terms)⏟∈ I1.1 = \underbrace{b_2 b_3 \cdots b_n}_{\in\, K} + \underbrace{(\text{sum of remaining terms})}_{\in\, I_1}.

This exhibits 11 as a sum of an element of KK and an element of I1I_1, so 1∈I1+K1 \in I_1 + K, and since I1+KI_1 + K is an ideal containing 11, I1+K=RI_1 + K = R. This proves I1I_1 and KK are comaximal. Applying the base case (n=2n=2 theorem) to I1I_1 and KK:

R/(I1∩K)  ≅  R/I1×R/K.R/(I_1 \cap K) \;\cong\; R/I_1 \times R/K.

Combining with (∗)(\ast), and using I1∩K=I1∩I2∩⋯∩InI_1 \cap K = I_1 \cap I_2 \cap \cdots \cap I_n (associativity of intersection), we obtain

R/⋂k=1nIk  ≅  R/I1×(R/I2×⋯×R/In)  ≅  ∏k=1nR/Ik,R \Big/ \bigcap_{k=1}^n I_k \;\cong\; R/I_1 \times (R/I_2 \times \cdots \times R/I_n) \;\cong\; \prod_{k=1}^n R/I_k,

where the last step identifies A×(B×C×⋯ )A \times (B \times C \times \cdots) with A×B×C×⋯A \times B \times C \times \cdots via the evident (associativity of finite products) ring isomorphism (a,(b2,…,bn))↦(a,b2,…,bn)(a,(b_2,\dots,b_n)) \mapsto (a,b_2,\dots,b_n), which is trivially a bijective ring homomorphism since operations on both sides are entrywise. Tracing through, the composite isomorphism sends r+⋂kIkr + \bigcap_k I_k to (r+I1,…,r+In)(r+I_1,\dots,r+I_n) as claimed. This completes the induction. Commutative case: If RR is commutative, apply Part 3 of the two-ideal theorem at each step of the induction: I1∩K=I1KI_1 \cap K = I_1 K (since I1,KI_1, K comaximal), and inductively K=I2I3⋯InK = I_2 I_3 \cdots I_n. Since ideal multiplication is associative in a commutative ring (an immediate consequence of the definitions in Operations on Ideals: Sum, Product, Intersection), I1∩⋯∩In=I1(I2⋯In)=I1I2⋯InI_1 \cap \cdots \cap I_n = I_1(I_2\cdots I_n) = I_1 I_2 \cdots I_n. ■\blacksquare

∎

Worked examples

Example 1: Three simultaneous congruences in Z\mathbb{Z}. Solve for xx:

x≡2(mod5),x≡3(mod7),x≡4(mod9).x \equiv 2 \pmod 5, \qquad x \equiv 3 \pmod 7, \qquad x \equiv 4 \pmod 9.

Here I1=(5)I_1 = (5), I2=(7)I_2 = (7), I3=(9)I_3 = (9) in R=ZR = \mathbb{Z}. Since gcd⁡(5,7)=gcd⁡(5,9)=gcd⁡(7,9)=1\gcd(5,7)=\gcd(5,9)=\gcd(7,9)=1, each pair generates comaximal ideals: e.g. (5)+(7)=(gcd⁡(5,7))=(1)=Z(5)+(7) = (\gcd(5,7)) = (1) = \mathbb{Z}, since Z\mathbb{Z} is a PID and (m)+(n)=(gcd⁡(m,n))(m)+(n) = (\gcd(m,n)). So I1,I2,I3I_1,I_2,I_3 are pairwise comaximal, and I1∩I2∩I3=(5⋅7⋅9)=(315)I_1 \cap I_2 \cap I_3 = (5\cdot7\cdot9) = (315) since these are pairwise coprime moduli (equivalently, lcm⁡(5,7,9)=315\operatorname{lcm}(5,7,9) = 315). The Corollary gives

Z/315Z  ≅  Z/5Z×Z/7Z×Z/9Z.\mathbb{Z}/315\mathbb{Z} \;\cong\; \mathbb{Z}/5\mathbb{Z} \times \mathbb{Z}/7\mathbb{Z} \times \mathbb{Z}/9\mathbb{Z}.

We now construct the solution using the proof's method, rather than guessing. Let M=315=5⋅7⋅9M = 315 = 5\cdot7\cdot9. For each modulus, form Mi=M/niM_i = M / n_i and find Mi−1  niM_i^{-1} \bmod n_i:

  • M1=315/5=63M_1 = 315/5 = 63. Need 63y1≡1(mod5)63 y_1 \equiv 1 \pmod 5. Since 63≡3(mod5)63 \equiv 3 \pmod 5, solve 3y1≡1(mod5)3y_1 \equiv 1 \pmod5: y1=2y_1 = 2 works (3⋅2=6≡13\cdot2=6\equiv1).
  • M2=315/7=45M_2 = 315/7 = 45. Need 45y2≡1(mod7)45 y_2 \equiv 1 \pmod 7. Since 45≡3(mod7)45 \equiv 3 \pmod 7, solve 3y2≡1(mod7)3y_2\equiv1\pmod7: y2=5y_2 = 5 works (3⋅5=15≡13\cdot5=15\equiv1).
  • M3=315/9=35M_3 = 315/9 = 35. Need 35y3≡1(mod9)35 y_3 \equiv 1 \pmod 9. Since 35≡8≡−1(mod9)35 \equiv 8 \equiv -1 \pmod 9, solve −y3≡1(mod9)-y_3 \equiv 1 \pmod 9: y3=−1≡8y_3 = -1 \equiv 8 works.

This is exactly the "e,fe,f" construction from the proof generalized to three factors: MiyiM_i y_i plays the role of the idempotent that is 11 mod nin_i and 00 mod the other moduli. The solution is

x≡2⋅63⋅2+3⋅45⋅5+4⋅35⋅8(mod315).x \equiv 2\cdot 63\cdot 2 + 3\cdot 45\cdot 5 + 4\cdot 35\cdot 8 \pmod{315}.

Compute each term: 2⋅63⋅2=2522\cdot63\cdot2 = 252; 3⋅45⋅5=6753\cdot45\cdot5 = 675; 4⋅35⋅8=11204\cdot35\cdot8 = 1120. Sum: 252+675+1120=2047252+675+1120 = 2047. Reduce mod 315: 2047=6⋅315+1572047 = 6\cdot315 + 157 (since 6⋅315=18906\cdot315 = 1890, and 2047−1890=1572047-1890=157). So x≡157(mod315)x \equiv 157 \pmod{315}. Check: 157=31⋅5+2157 = 31\cdot5 + 2, so 157≡2(mod5)157 \equiv 2 \pmod 5. ✓. 157=22⋅7+3157 = 22\cdot7+3, so 157≡3(mod7)157\equiv3\pmod7. ✓. 157=17⋅9+4157 = 17\cdot9+4, so 157≡4(mod9)157\equiv4\pmod9. ✓. All three congruences hold, confirming the isomorphism's inverse construction is correct.

Example 2: Polynomial ring over Q\mathbb{Q}. Let R=Q[x]R = \mathbb{Q}[x], and let I=(x−1)I = (x-1), J=((x−2)(x−3))=(x2−5x+6)J = ((x-2)(x-3)) = (x^2-5x+6). These are comaximal: in Q[x]\mathbb{Q}[x], a PID, (f)+(g)=(gcd⁡(f,g))(f)+(g) = (\gcd(f,g)), and gcd⁡(x−1, (x−2)(x−3))=1\gcd(x-1,\ (x-2)(x-3)) = 1 since x=1x=1 is not a root of (x−2)(x−3)(x-2)(x-3) (indeed (1−2)(1−3)=(−1)(−2)=2≠0(1-2)(1-3) = (-1)(-2) = 2 \neq 0). Concretely we exhibit a∈I,b∈Ja\in I, b\in J with a+b=1a+b=1: we want polynomials u,vu,v with

u(x)(x−1)+v(x)(x−2)(x−3)=1.u(x)(x-1) + v(x)(x-2)(x-3) = 1.

Try v(x)=cv(x) = c constant: we need u(x)(x−1)=1−c(x−2)(x−3)u(x)(x-1) = 1 - c(x-2)(x-3). Evaluate at x=1x=1: the right side must vanish's-worth... actually we just need the right side divisible by (x−1)(x-1), i.e. equal to 00 at x=1x=1: 1−c(1−2)(1−3)=1−c(2)=0⇒c=121 - c(1-2)(1-3) = 1 - c(2) = 0 \Rightarrow c = \tfrac12. So v(x)=12v(x) = \tfrac12, and

1−12(x−2)(x−3)=1−12(x2−5x+6)=−12x2+52x−2.1 - \tfrac12(x-2)(x-3) = 1 - \tfrac12(x^2-5x+6) = -\tfrac12 x^2 + \tfrac52 x - 2.

Divide by (x−1)(x-1): −12x2+52x−2=(x−1)(−12x+2)-\tfrac12x^2+\tfrac52x-2 = (x-1)(-\tfrac12x + 2) — check by expanding: (x−1)(−12x+2)=−12x2+2x+12x−2=−12x2+52x−2(x-1)(-\tfrac12x+2) = -\tfrac12x^2+2x+\tfrac12x-2 = -\tfrac12x^2+\tfrac52x-2. ✓. So u(x)=−12x+2u(x) = -\tfrac12x+2. Thus a=u(x)(x−1)=−12x2+52x−2∈Ia = u(x)(x-1) = -\tfrac12x^2+\tfrac52x-2 \in I and b=12(x−2)(x−3)∈Jb = \tfrac12(x-2)(x-3) \in J, with a+b=1a+b=1 (check: b=12x2−52x+3b = \tfrac12x^2 - \tfrac52x+3, so a+b=(−12+12)x2+(52−52)x+(−2+3)=1a+b = (-\tfrac12+\tfrac12)x^2 + (\tfrac52-\tfrac52)x + (-2+3) = 1 ✓). By the theorem, Q[x]/(I∩J)≅Q[x]/I×Q[x]/J\mathbb{Q}[x]/(I\cap J) \cong \mathbb{Q}[x]/I \times \mathbb{Q}[x]/J. Since gcd⁡(x−1,(x−2)(x−3))=1\gcd(x-1, (x-2)(x-3))=1 and Q[x]\mathbb{Q}[x] is a UFD, I∩J=(lcm⁡(x−1,(x−2)(x−3)))=((x−1)(x−2)(x−3))I \cap J = (\operatorname{lcm}(x-1,(x-2)(x-3))) = ((x-1)(x-2)(x-3)). Both sides are 3-dimensional Q\mathbb{Q}-vector spaces: Q[x]/(x−1)≅Q\mathbb{Q}[x]/(x-1) \cong \mathbb{Q} (evaluation at 11), similarly Q[x]/((x−2)(x−3))\mathbb{Q}[x]/((x-2)(x-3)) is 2-dimensional, and Q[x]/((x−1)(x−2)(x−3))\mathbb{Q}[x]/((x-1)(x-2)(x-3)) is 3-dimensional, matching 1+2=31+2=3. Concretely, this isomorphism is the map

p(x)+(x−1)(x−2)(x−3) ⟼ (p(1), p(x)  (x−2)(x−3)),p(x) + (x-1)(x-2)(x-3) \ \longmapsto\ \big(p(1),\ p(x) \bmod (x-2)(x-3)\big),

i.e. evaluating at the simple root and reducing modulo the quadratic factor — a Lagrange-interpolation-style reconstruction, since specifying p(1)p(1) and p(x)  (x−2)(x−3)p(x) \bmod (x-2)(x-3) (equivalently p(2),p(3)p(2), p(3)) uniquely pins down p(x)  (x−1)(x−2)(x−3)p(x) \bmod (x-1)(x-2)(x-3), i.e. determines the unique degree ≤2\le 2 interpolant through three points (1,p(1)),(2,p(2)),(3,p(3))(1,p(1)), (2,p(2)), (3,p(3)).

CounterexampleDropping comaximality: I,JI,J not comaximal breaks surjectivity

Let R=ZR = \mathbb{Z}, I=(4)I = (4), J=(6)J = (6). These are not comaximal: I+J=(4)+(6)=(gcd⁡(4,6))=(2)≠ZI + J = (4) + (6) = (\gcd(4,6)) = (2) \neq \mathbb{Z}, since 22 is not a unit in Z\mathbb{Z}. The map φ:Z→Z/4Z×Z/6Z\varphi:\mathbb{Z} \to \mathbb{Z}/4\mathbb{Z}\times\mathbb{Z}/6\mathbb{Z}, φ(r)=(r  4, r  6)\varphi(r) = (r\bmod4,\ r\bmod6), still has ker⁡φ=(4)∩(6)=(12)\ker\varphi = (4)\cap(6) = (12) (since lcm⁡(4,6)=12\operatorname{lcm}(4,6)=12), by Part 1 of the theorem, which needs no comaximality. But φ\varphi is not surjective: consider the target (0, 1)∈Z/4Z×Z/6Z(0,\,1) \in \mathbb{Z}/4\mathbb{Z}\times\mathbb{Z}/6\mathbb{Z}, i.e. we ask for rr with r≡0(mod4)r\equiv0\pmod4 and r≡1(mod6)r\equiv1\pmod6. If r≡0(mod4)r \equiv 0 \pmod 4 then rr is even, so r≡0,2,r \equiv 0, 2, or 4(mod6)4 \pmod 6 — never 11 (mod 6), because rr even forces r  6∈{0,2,4}r \bmod 6 \in \{0,2,4\}, an even residue, while 11 is odd. So no such rr exists, and (0,1)(0,1) has no preimage. Consequently φ(Z)\varphi(\mathbb{Z}) is a proper subgroup (in fact subring) of Z/4×Z/6\mathbb{Z}/4\times\mathbb{Z}/6, of index 22 — one checks ∣Z/12Z∣=12|\mathbb{Z}/12\mathbb{Z}| = 12 while ∣Z/4×Z/6∣=24|\mathbb{Z}/4\times\mathbb{Z}/6| = 24, so the induced injective map φˉ:Z/12Z↪Z/4×Z/6\bar\varphi:\mathbb{Z}/12\mathbb{Z}\hookrightarrow \mathbb{Z}/4\times\mathbb{Z}/6 (injective by Part 1, since ker⁡φ=(12)\ker\varphi = (12), via the First Isomorphism Theorem) cannot be surjective purely by a cardinality count, confirming the failure without needing to check every element. This shows the comaximality hypothesis in Part 2 is not merely convenient but essential: without it, the natural comparison map exists and is still injective on the quotient, but the product ring is strictly larger than R/(I∩J)R/(I\cap J) can reach, so no isomorphism R/(I∩J)≅R/I×R/JR/(I\cap J) \cong R/I \times R/J is possible.

Scope, edge cases & common traps

SituationWhat happens
I,JI,J comaximal, RR noncommutativeTheorem holds (Parts 1–2); Part 3 (I∩J=IJI\cap J = IJ) needs commutativity and can fail otherwise.
I,JI,J not comaximalφ\varphi still a homomorphism with kernel I∩JI\cap J, but generally not surjective (see counterexample).
n≥3n \geq 3 ideals, jointly but not pairwise comaximalCorollary's proof needs pairwise comaximality; joint comaximality of the whole set alone does not suffice for the inductive step.
RR without identityThe witnessing equation e+f=1e+f=1 has no meaning; theorem as stated does not apply.
I=JI = JComaximal only if I=J=RI = J = R (trivial ring case), since I+J=II+J=I here.

The mathematician behind it

Origins · 1 minSun Zi (孙子) and how this was discovered
SZ
Sun Zi (孙子)
circa 3rd–5th century CE · Chinese mathematics, Sunzi Suanjing

The problem "we have things of unknown number... find the number of things" appears in the Sunzi Suanjing (Master Sun's Mathematical Manual), a foundational Chinese arithmetic text. Sun Zi is a name attached to this text rather than a fully documented historical individual with a modern-style biography; the text's exact date is debated by historians, placed anywhere from the 3rd to 5th century CE. The manual poses and solves the prototype simultaneous-congruence problem — remainders 2, 3, 2 upon division by 3, 5, 7 — using a method equivalent in substance to the constructive proof given above, centuries before ring theory existed to explain why the method works.

History
- 3rd–5th century CE — The Sunzi Suanjing states and solves the prototypical simultaneous-remainder problem.
- 1247 — Qin Jiushao's Shùshū Jiǔzhāng (Mathematical Treatise in Nine Sections) gives a general algorithm, "Dayan rule," for arbitrary moduli, going well beyond Sun Zi's special case.
- 1801 — Carl Friedrich Gauss, in Disquisitiones Arithmeticae, systematizes congruences and reproves the classical CRT within modern number-theoretic notation.
- Late 19th–early 20th century — Richard Dedekind and Emmy Noether's development of ideal theory recasts CRT as a statement about comaximal ideals in general rings, detached from Z\mathbb{Z}.
- 20th century onward — The ring-theoretic CRT becomes a standard structural tool across commutative algebra, algebraic number theory, and algebraic geometry.
Why is the condition called "comaximal" rather than just "coprime"?

"Coprime" is the classical number-theoretic term for integers with gcd⁡=1\gcd=1, which translates to ideals (m),(n)(m),(n) satisfying (m)+(n)=Z(m)+(n)=\mathbb{Z}. "Comaximal" is the ring-theoretic generalization: it says I+JI+J equals the whole ring RR, i.e. I+JI+J is not contained in any proper ideal, hence not contained in any maximal ideal — the two ideals share no common "constraint." The term emphasizes that the sum ideal is maximal in the strongest sense (equal to RR), which is the right generalization once you leave Z\mathbb{Z} and no longer have a single gcd function to appeal to.

Does the theorem require RR to be commutative?

No — Parts 1 and 2 (the isomorphism R/(I∩J)≅R/I×R/JR/(I\cap J)\cong R/I\times R/J) hold for any ring with identity, with I,JI,J two-sided ideals. Commutativity is only needed for Part 3, the extra fact that I∩J=IJI\cap J = IJ when I,JI,J are comaximal. In a noncommutative ring, IJIJ and JIJI can genuinely differ, and the clean identification of the intersection with a single product ideal can fail, though the isomorphism with R/I×R/JR/I\times R/J itself still goes through via I∩JI \cap J.

How does this relate to solving x≡a(modm)x \equiv a \pmod m, x≡b(modn)x \equiv b \pmod n in elementary number theory?

That classical statement is exactly the case R=ZR=\mathbb{Z}, I=(m)I=(m), J=(n)J=(n), with gcd⁡(m,n)=1\gcd(m,n)=1 translating to I+J=ZI+J=\mathbb{Z}. The isomorphism Z/mnZ≅Z/mZ×Z/nZ\mathbb{Z}/mn\mathbb{Z}\cong\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z} is precisely the statement that every pair of residues (a  m, b  n)(a\bmod m,\ b\bmod n) arises from a unique residue x  mnx \bmod mn. The explicit construction using e,fe,f with e+f=1e+f=1 becomes the familiar formula x≡aN2M2+bN1M1(modmn)x \equiv aN_2M_2 + bN_1M_1 \pmod{mn} used in elementary courses, where M1,M2M_1,M_2 and their inverses play the role of f,ef,e.

What goes wrong if we only assume I∩J=0I \cap J = 0 instead of I+J=RI+J=R?

Assuming I∩J=0I\cap J=0 only guarantees φ\varphi is injective (since ker⁡φ=I∩J=0\ker\varphi = I\cap J = 0), giving an embedding R↪R/I×R/JR \hookrightarrow R/I\times R/J, but says nothing about surjectivity. Without I+J=RI+J=R, the image of φ\varphi can be a proper subring of the product, exactly as in the counterexample with I=(4),J=(6)I=(4),J=(6) where in fact I∩J=(12)≠0I \cap J = (12) \ne 0 too — but even engineering examples with trivial intersection and non-comaximal sum, surjectivity is not guaranteed, because surjectivity was proved using the explicit element af+beaf+be, which requires the decomposition 1=e+f1=e+f coming from I+J=RI+J=R.

Can CRT be stated for modules instead of rings?

Yes, in a related but distinct form: if MM is an RR-module and I,JI,J are comaximal ideals, then M/(I∩J)M≅M/IM×M/JMM/(I\cap J)M \cong M/IM \times M/JM as RR-modules, by essentially the same proof applied to the module map m↦(m+IM,m+JM)m \mapsto (m+IM, m+JM). This module-level CRT is used in the structure theorem for finitely generated modules over a PID, where a module is decomposed according to prime-power components, mirroring how Z/nZ\mathbb{Z}/n\mathbb{Z} decomposes via CRT.

Is the isomorphism in CRT unique, or does it depend on choices?

The isomorphism φˉ\bar\varphi itself is canonical — it is entirely determined by the ideals I,JI,J and does not depend on any choice of e,fe,f. What depends on a choice is the explicit formula for the inverse map (reconstructing an element from a target pair), since the equation e+f=1e+f=1 need not have a unique solution pair (e,f)(e,f) with e∈I,f∈Je \in I, f \in J in general. Any valid choice of such e,fe,f gives a correct reconstruction formula, and the resulting element is well-defined modulo I∩JI \cap J, consistent with the theorem.

Before this