Chapter 16

Hard

Chinese Remainder Theorem

00 · Symbol Glossary

$I+J=R$Comaximal ideals

Two ideals whose sum is the entire ring — the ring-theoretic generalization of two integers being coprime ( $\gcd(m,n)=1 \iff m\mathbb{Z}+n\mathbb{Z}=\mathbb{Z}$ , Chapter 12).

$I\cap J$Intersection of two ideals (recalled)

Always an ideal (Theorem 12.3), corresponding to $\mathrm{lcm}$ when $I,J$ are ideals of $\mathbb{Z}$ .

$R/I \times R/J$Direct product of quotient rings

The ring $R/I\times R/J$ from Chapter 07's direct product construction, applied to two quotient rings — the target of this chapter's central isomorphism.

01 · The Classical Statement

The Chinese Remainder Theorem is one of the oldest results in number theory, traditionally stated as: given coprime moduli, a system of congruences always has a unique simultaneous solution.

Example — The classical problem

Find $x$ with $x\equiv2\pmod3$ and $x\equiv3\pmod5$ . Checking $x=8$ : $8=3(2)+2$ ✓, $8=5(1)+3$ ✓. It works — and (as the classical theorem asserts) $8$ is the only solution modulo $15=3\times5$ .

This chapter recasts that classical fact as a ring isomorphism, using exactly the machinery built in Chapters 12 and 13 — and the generalization applies far beyond $\mathbb{Z}$ .

02 · Comaximal Ideals

Definition — Comaximal Ideals

Two ideals $I,J\trianglelefteq R$ are comaximal if $I+J=R$ .

Example — Comaximal ideals of Z are exactly coprime multiples

By Chapter 12's Section 04, $m\mathbb{Z}+n\mathbb{Z} = \gcd(m,n)\mathbb{Z}$ . This equals $\mathbb{Z}$ exactly when $\gcd(m,n)=1$ . $m\mathbb{Z}$ and $n\mathbb{Z}$ are comaximal precisely when $m,n$ are coprime — recovering the classical hypothesis of the Chinese Remainder Theorem as a special case of "comaximal."

03 · The General Chinese Remainder Theorem

Theorem 16.1 — Chinese Remainder Theorem (ring version)

If $I,J\trianglelefteq R$ are comaximal, then:

R/(I\cap J) \;\cong\; R/I \times R/J

Proof

Define $\varphi: R \to R/I\times R/J$ by $\varphi(a) = (a+I,\,a+J)$ .

Homomorphism. $\varphi(a+b) = (a+b+I,a+b+J) = (a+I,a+J)+(b+I,b+J) = \varphi(a)+\varphi(b)$ , and $\varphi(ab) = (ab+I,ab+J) = (a+I,a+J)(b+I,b+J) = \varphi(a)\varphi(b)$ (each coordinate is a quotient-ring homomorphism, Chapter 12). $\varphi(1)=(1+I,1+J)$ , the unity of the product ring.

Kernel. $\varphi(a)=(0+I,0+J)$ exactly when $a\in I$ and $a\in J$ , i.e. $a\in I\cap J$ . So $\ker\varphi = I\cap J$ — and by Theorem 13.3, this confirms independently that $I\cap J$ is an ideal (already known from Theorem 12.3).

Surjective. Since $I+J=R$ , write $1=i+j$ for some $i\in I,\,j\in J$ . Note $j = 1-i \equiv 1\pmod I$ (since $i\in I$ ) and $i=1-j\equiv1\pmod J$ (since $j\in J$ ). Given any target $(a+I,\,b+J)\in R/I\times R/J$ , let $x := aj+bi$ . Then:

x = aj+bi \equiv a\cdot1 + b\cdot0 = a \pmod I \qquad (\text{using } j\equiv1,\ i\equiv0 \bmod I)

So $\varphi(x) = (a+I,\,b+J)$ : every element of the target is hit.

By the First Isomorphism Theorem for rings (Theorem 13.6): $R/\ker\varphi \cong \mathrm{im}\,\varphi$ , and since $\varphi$ is surjective, $\mathrm{im}\,\varphi = R/I\times R/J$ . So $R/(I\cap J) \cong R/I\times R/J$ .

04 · Recovering the Classical Theorem

Example — Z/mnZ ≅ Z_m × Z_n, revisited

Let $I=m\mathbb{Z}$ , $J=n\mathbb{Z}$ with $\gcd(m,n)=1$ (comaximal, Section 02). By Chapter 12's Section 04, $I\cap J = \mathrm{lcm}(m,n)\mathbb{Z} = mn\mathbb{Z}$ (since $\gcd(m,n)=1$ gives $\mathrm{lcm}(m,n)=mn$ ). Theorem 16.1 gives:

\mathbb{Z}/mn\mathbb{Z} \;\cong\; \mathbb{Z}_m\times\mathbb{Z}_n

as rings — sharpening Theorem 7.3's group-only isomorphism $\mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n$ from Chapter 07 to include multiplication as well, exactly as Chapter 13's Example already did for the special case of a single prime power reduction.

Step-by-step — Solving x≡2 (mod 3), x≡3 (mod 5) via the proof's explicit formula

Find $i\in3\mathbb{Z}$ , $j\in5\mathbb{Z}$ with $i+j=1$ (Bézout, Theorem 15.2): try

6-5=1

, so

i=6\in3\mathbb{Z}

j=-5\in5\mathbb{Z}

Check the congruences $i,j$ should satisfy:

j=-5\equiv1\pmod3

(since

-5=3(-2)+1

) ✓;

i=6\equiv1\pmod5

(since

6=5(1)+1

) ✓.

Apply the formula $x=aj+bi$ with $a=2,b=3$ :

x = 2(-5)+3(6) = -10+18 = 8

Verify:

8\equiv2\pmod3

✓ (

8=3(2)+2

);

8\equiv3\pmod5

✓ (

8=5(1)+3

Conclusion:

x=8

solves the system, matching Section 01's Example — and by Theorem 16.1, this solution is unique modulo

15

(the isomorphism

\mathbb{Z}/15\mathbb{Z}\cong\mathbb{Z}_3\times\mathbb{Z}_5

is a bijection, so each target pair has exactly one preimage).

05 · Several Moduli at Once

Theorem 16.2 — CRT for k Pairwise Comaximal Ideals

If $I_1,\ldots,I_k\trianglelefteq R$ are pairwise comaximal ( $I_a+I_b=R$ for all $a\neq b$ ), then:

R/(I_1\cap\cdots\cap I_k) \;\cong\; R/I_1\times\cdots\times R/I_k

Proof

By induction on $k$ , with $k=2$ being Theorem 16.1. Assume the result for $k-1$ ideals, and let $J = I_1\cap\cdots\cap I_{k-1}$ . It suffices to show $J$ and $I_k$ are comaximal (then applying Theorem 16.1 to $J,I_k$ gives $R/(J\cap I_k) \cong R/J\times R/I_k$ , and $J\cap I_k = I_1\cap\cdots\cap I_k$ , with $R/J\cong R/I_1\times\cdots\times R/I_{k-1}$ by the induction hypothesis).

Since $I_a+I_k=R$ for each $a<k$ , write $1=x_a+y_a$ with $x_a\in I_a$ , $y_a\in I_k$ . Then $\prod_{a=1}^{k-1}(x_a+y_a) = 1$ ; expanding, every term except $\prod_a x_a$ contains at least one factor $y_a\in I_k$ , so every term except that one lies in $I_k$ (absorption applied within the product structure). And $\prod_a x_a \in I_1\cdots I_{k-1} \subseteq I_1\cap\cdots\cap I_{k-1}=J$ (a product of elements from each $I_a$ lies in every $I_a$ , since each individual $I_a$ absorbs the other factors). So $1 = (\text{element of } J) + (\text{element of } I_k) \in J+I_k$ , giving $J+I_k=R$ : comaximal.

Example — Three simultaneous congruences

$\mathbb{Z}/30\mathbb{Z} \cong \mathbb{Z}_2\times\mathbb{Z}_3\times\mathbb{Z}_5$ (since $2,3,5$ are pairwise coprime, hence $2\mathbb{Z},3\mathbb{Z},5\mathbb{Z}$ pairwise comaximal, and $2\mathbb{Z}\cap3\mathbb{Z}\cap5\mathbb{Z}=30\mathbb{Z}$ ). A system like $x\equiv1\pmod2$ , $x\equiv2\pmod3$ , $x\equiv3\pmod5$ has a unique solution mod 30 (which turns out to be $x=23$ : check $23=2(11)+1$ , $23=3(7)+2$ , $23=5(4)+3$ ✓✓✓), guaranteed to exist by Theorem 16.2 without needing to search.

06 · Exercises

EXERCISE 16.1

Compute $\gcd(4,9)$ first to check comaximality, then compute $\mathrm{lcm}(4,9)$ for the intersection.

$\gcd(4,9)=1$ , so $4\mathbb{Z}$ and $9\mathbb{Z}$ are comaximal (Section 02). $\mathrm{lcm}(4,9)=36$ , so $4\mathbb{Z}\cap9\mathbb{Z}=36\mathbb{Z}$ . By Theorem 16.1: $\mathbb{Z}/36\mathbb{Z} \cong \mathbb{Z}_4\times\mathbb{Z}_9$ .

State the isomorphism given by Theorem 16.1 for $I=4\mathbb{Z}$ , $J=9\mathbb{Z}$ .

EXERCISE 16.2

Follow the exact steps of the Section 04 worked example: find Bézout coefficients for $\gcd(4,9)=1$ first.

Find $i\in4\mathbb{Z}$ , $j\in9\mathbb{Z}$ with $i+j=1$ : $1 = 9(1) + 4(-2)$ , so $j=9$ , $i=-8$ . Check: $j=9\equiv1\pmod4$ ✓; $i=-8\equiv1\pmod9$ ✓ ( $-8=9(-1)+1$ ).

Apply $x=aj+bi$ with $a=1,b=2$ : $x = 1(9)+2(-8) = 9-16=-7 \equiv 29\pmod{36}$ .

Check: $29 = 4(7)+1$ ✓; $29=9(3)+2$ ✓.

Solve $x\equiv1\pmod4$ , $x\equiv2\pmod9$ using the explicit construction from Theorem 16.1's proof.

EXERCISE 16.3

Check whether $6\mathbb{Z}$ and $9\mathbb{Z}$ are comaximal first — this determines whether Theorem 16.1 even applies.

$6\mathbb{Z}+9\mathbb{Z} = \gcd(6,9)\mathbb{Z} = 3\mathbb{Z} \neq \mathbb{Z}$ . Not comaximal — Theorem 16.1 does not apply to $I=6\mathbb{Z}$ , $J=9\mathbb{Z}$ .

The naive isomorphism fails for the bluntest possible reason: $\lvert\mathbb{Z}/18\mathbb{Z}\rvert = 18$ but $\lvert\mathbb{Z}_6\times\mathbb{Z}_9\rvert = 54$ , and isomorphic rings must have the same number of elements.

Tracing where the proof breaks is more instructive. The map $\varphi:\mathbb{Z}\to\mathbb{Z}_6\times\mathbb{Z}_9$ , $\varphi(a)=(a+6\mathbb{Z},\,a+9\mathbb{Z})$ , is still a homomorphism, and its kernel is still $6\mathbb{Z}\cap9\mathbb{Z} = \mathrm{lcm}(6,9)\mathbb{Z} = 18\mathbb{Z}$ , so the First Isomorphism Theorem still gives $\mathbb{Z}/18\mathbb{Z}\cong\mathrm{im}\,\varphi$ . What fails is surjectivity: the proof of Theorem 16.1 produced a preimage using $1=i+j$ with $i\in I$ , $j\in J$ , and no such decomposition exists here, since $6\mathbb{Z}+9\mathbb{Z}=3\mathbb{Z}$ does not contain $1$ . So $\mathrm{im}\,\varphi$ is a proper subring of $\mathbb{Z}_6\times\mathbb{Z}_9$ — of size 18 inside 54, index 3. Comaximality is exactly the hypothesis that buys surjectivity.

Explain why Theorem 16.1 does not apply to $I=6\mathbb{Z}$ , $J=9\mathbb{Z}$ , and what goes wrong with the naive isomorphism $\mathbb{Z}/18\mathbb{Z}\cong\mathbb{Z}_6\times\mathbb{Z}_9$ .

EXERCISE 16.4

Apply Theorem 16.2 with three pairwise coprime moduli.

$7,11,13$ are pairwise coprime (all distinct primes). By Theorem 16.2:

$\mathbb{Z}/1001\mathbb{Z} \;\cong\; \mathbb{Z}_7\times\mathbb{Z}_{11}\times\mathbb{Z}_{13}$

(using $7\times11\times13=1001$ ), guaranteeing a unique solution mod 1001 to any system $x\equiv a\pmod7$ , $x\equiv b\pmod{11}$ , $x\equiv c\pmod{13}$ .

Using Theorem 16.2, state the isomorphism for $\mathbb{Z}/1001\mathbb{Z}$ , given $1001=7\times11\times13$ .

07 · Chapter Summary

Concept	Statement
Comaximal ideals	$I+J=R$ ; generalizes $\gcd(m,n)=1$
CRT (ring version)	$I,J$ comaximal $\implies R/(I\cap J)\cong R/I\times R/J$ (Thm 16.1)
Explicit solution	$x=aj+bi$ where $i+j=1$ , $i\in I$ , $j\in J$
Classical CRT	$\gcd(m,n)=1 \implies \mathbb{Z}/mn\mathbb{Z}\cong\mathbb{Z}_m\times\mathbb{Z}_n$ , as rings
k-fold CRT	Pairwise comaximal $I_1,\ldots,I_k \implies R/\bigcap I_a \cong \prod R/I_a$ (Thm 16.2)

Next: Chapter 17 — Fields begins the third arc of the course: rings where every nonzero element is invertible, the natural stopping point where division becomes fully available.