CRT in General

Recall that all rings in this book are commutative with unity.

Definition 5.1.1 (Coprime)   Ideals $ I$ and $ J$ are coprime if $ I+J=(1)$.

If $ I$ and $ J$ are nonzero ideals in the ring of integers of a number field, then they are coprime precisely when the prime ideals that appear in their two (unique) factorizations are disjoint.

Lemma 5.1.2   If $ I$ and $ J$ are coprime ideals in a ring $ R$, then $ I\cap{}J = IJ$.

Proof. Choose $ x\in I$ and $ y\in J$ such that $ x+y=1$. If $ c\in{} I\cap{} J$ then

$\displaystyle c=c\cdot 1=c\cdot (x+y) = cx + cy \in IJ + IJ = IJ,$

so $ I\cap{} J\subset IJ$. The other inclusion is obvious by definition of ideal. $ \qedsymbol$

Lemma 5.1.3   Suppose $ I_1,\ldots, I_s$ are pairwise coprime ideals. Then $ I_1$ is coprime to the product $ I_2\cdots I_s$.

Proof. It suffices to prove the lemma in the case $ s=3$, since the general case then follows from induction. By assumption, there are $ x_1 \in I_1, y_2 \in I_2$ and $ a_1 \in I_1, b_3 \in I_3$ such

$\displaystyle x_1 + y_2 = 1$   and$\displaystyle \qquad a_1 + b_3 = 1.

Multiplying these two relations yields

$\displaystyle x_1 a_1 + x_1 b_3 + y_2 a_1 + y_2 b_3 = 1 \cdot 1 = 1.

The first three terms are in $ I_1$ and the last term is in $ I_2 I_3 = I_2 \cap I_3$ (by Lemma 5.1.2), so $ I_1$ is coprime to $ I_2 I_3$. $ \qedsymbol$

Next we prove the general Chinese Remainder Theorem. We will apply this result with $ R=\O_K$ in the rest of this chapter.

Theorem 5.1.4 (Chinese Remainder Theorem)   Suppose $ I_1,\ldots, I_r$ are nonzero ideals of a ring $ R$ such $ I_m$ and $ I_n$ are coprime for any $ m\neq n$. Then the natural homomorphism $ R \to \bigoplus_{n=1}^r R/I_n$ induces an isomorphism

$\displaystyle \psi: R/\prod_{n=1}^r I_n \to \bigoplus_{n=1}^r R/I_n.

Thus given any $ a_n \in R$, for $ n=1,\ldots,r$, there exists some $ a\in R$ such that $ a\equiv a_n\pmod{I_n}$ for $ n=1,\ldots,r$; moreover, $ a$ is unique modulo $ \prod_{n=1}^r I_n$.

Proof. Let $ \varphi :R \to \bigoplus_{n=1}^r R/I_n
$ be the natural map induced by reduction modulo the $ I_n$. An inductive application of Lemma 5.1.2 implies that the kernel $ \cap_{n=1}^r I_n$ of $ \varphi $ is equal to $ \prod_{n=1}^r I_n$, so the map $ \psi$ of the theorem is injective.

Each projection $ R\to R/I_n$ is surjective, so to prove that $ \psi$ is surjective, it suffices to show that $ (1,0,\ldots,0)$ is in the image of $ \varphi $, and similarly for the other factors. By Lemma 5.1.3, $ J=\prod_{n=2}^rI_n$ is coprime to $ I_1$, so there exists $ x\in I_1$ and $ y\in J$ such that $ x+y=1$. Then $ y = 1-x$ maps to $ 1$ in $ R/I_1$ and to 0 in $ R/J$, hence to 0 in $ R/I_n$ for each $ n\geq 2$, since $ J\subset I_n$. $ \qedsymbol$

William Stein 2012-09-24