The Chinese Remainder Theorem

Recall that the Chinese Remainder Theorem from elementary number theory asserts that if $ n_1,\ldots, n_r$ are integers that are coprime in pairs, and $ a_1,\ldots, a_r$ are integers, then there exists an integer $ a$ such that $ a\equiv a_i\pmod{n_i}$ for each $ i=1,\ldots,r$. In terms of rings, the Chinese Remainder Theorem asserts that the natural map

$\displaystyle \mathbf{Z}/(n_1\cdots n_r)\mathbf{Z}\to (\mathbf{Z}/n_1\mathbf{Z})\oplus \cdots \oplus (\mathbf{Z}/n_r\mathbf{Z})

is an isomorphism. This result generalizes to rings of integers of number fields.

Lemma 9.1.1   If $ I$ and $ J$ are coprime ideals in $ \O _K$, then $ I\cap{}J = IJ$.

Proof. The ideal $ I\cap{}J$ is the largest ideal of $ \O _K$ that is divisible by (contained in) both $ I$ and $ J$. Since $ I$ and $ J$ are coprime, $ I\cap{}J$ is divisible by $ IJ$, i.e., $ I\cap{}J\subset IJ$. By definition of ideal $ IJ\subset I\cap{}J$, which completes the proof. $ \qedsymbol$

Remark 9.1.2   This lemma is true for any ring $ R$ and ideals $ I,J\subset R$ such that $ I+J=R$. For the general 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$, and the other inclusion is obvious by definition.

Theorem 9.1.3 (Chinese Remainder Theorem)   Suppose $ I_1,\ldots, I_r$ are ideals of $ \O _K$ such that $ I_m+I_n=\O _K$ for any $ m\neq n$. Then the natural homomorphism $ \O _K \to \bigoplus_{n=1}^r (\O _K/I_n)$ induces an isomorphism

$\displaystyle \O _K/\left(\prod_{n=1}^r I_n\right) \to \bigoplus_{n=1}^r (\O _K/I_n).

Thus given any $ a_n \in I_n$ then there exists $ a\in\O _K$ such that $ a\equiv a_n\pmod{I_n}$ for $ n=1,\ldots, r$.

Proof. First assume that we know the theorem in the case when the $ I_n$ are powers of prime ideals. Then we can deduce the general case by noting that each $ \O _K/I_n$ is isomorphic to a product $ \prod
\O _K/\mathfrak{p}_{m}^{e_{m}}$, where $ I_n=\prod \mathfrak{p}_{m}^{e_{m}}$, and $ \O _K/(\prod_n I_n)$ is isomorphic to the product of the $ \O _K/\mathfrak{p}^e$, where the $ \mathfrak{p}$ and $ e$ run through the same prime powers as appear on the right hand side.

It thus suffices to prove that if $ \mathfrak{p}_1,\ldots, \mathfrak{p}_r$ are distinct prime ideals of $ \O _K$ and $ e_1,\ldots, e_r$ are positive integers, then

$\displaystyle \psi: \O _K/\left(\prod_{n=1}^r \mathfrak{p}_n^{e_n} \right)
\to \bigoplus_{n=1}^r (\O _K/\mathfrak{p}_n^{e_n})

is an isomorphism. Let $ \varphi :\O _K \to \oplus_{n=1}^r
(\O _K/\mathfrak{p}_n^{e_n})$ be the natural map induced by reduction mod $ \mathfrak{p}_n^{e_n}$. Then kernel of $ \varphi $ is $ \cap_{n=1}^r \mathfrak{p}_n^{e_n}$, which by Lemma 9.1.1 is equal to $ \prod_{n=1}^r
\mathfrak{p}_n^{e_n}$, so $ \psi$ is injective. Note that the projection $ \O _K\to \O _K/\mathfrak{p}_n^{e_n}$ of $ \varphi $ onto each factor is obviously surjective, so it suffices to show that the element $ (1,0,\ldots,0)$ is in the image of $ \varphi $ (and the similar elements for the other factors). Since $ J=\prod_{n=2}^r\mathfrak{p}_n^{e_n}$ is not divisible by $ \mathfrak{p}_1$, hence not contained in $ \mathfrak{p}_1$, there is an element $ a\in{}J$ with $ a\not\in\mathfrak{p}_1$. Since $ \mathfrak{p}_1$ is maximal, $ \O _K/\mathfrak{p}_1$ is a field, so there exists $ b\in \O _K$ such that $ ab=1-c$, for some $ c\in\mathfrak{p}_1$. Then

$\displaystyle 1-c^{n_1} = (1-c)(1+c+c^2 + \cdots +c^{n_1-1})
=ab(1+c+c^2 + \cdots +c^{n_1-1})$

is congruent to 0 mod $ \mathfrak{p}_n^{e_n}$ for each $ n\geq 2$ since it is in $ \prod_{n=2}^r \mathfrak{p}_n^{e_n}$, and it is congruent to $ 1$ modulo $ \mathfrak{p}_1^{n_1}$. $ \qedsymbol$

Remark 9.1.4   In fact, the surjectivity part of the above proof is easy to prove for any commutative ring; indeed, the above proof illustrates how trying to prove something in a special case can result in a more complicated proof!! Suppose $ R$ is a ring and $ I,J$ are ideals in $ R$ such that $ I+J=R$. Choose $ x\in I$ and $ y\in J$ such that $ x+y=1$. Then $ x=1-y$ maps to $ (0,1)$ in $ R/I \oplus R/J$ and $ y=1-x$ maps to $ (1,0)$ in $ R/I \oplus R/J$. Thus the map $ R/(I\cap
J) \to R/I\oplus R/J$ is surjective. Also, as mentioned above, $ R/(I\cap{}J)=R/(IJ)$.

Example 9.1.5   The command ChineseRemainderTheorem implements the algorithm suggested by the above theorem. In the following example, we compute a prime over $ (3)$ and a prime over $ (5)$ of the ring of integers of $ \mathbf{Q}(\sqrt[3]{2})$, and find an element of $ \O _K$ that is congruent to $ \sqrt[3]{2}$ modulo one prime and $ 1$ modulo the other.
   > R<x> := PolynomialRing(RationalField());
   > K<a> := NumberField(x^3-2);
   > OK := MaximalOrder(K);
   > I := Factorization(3*OK)[1][1];
   > J := Factorization(5*OK)[1][1];
   > I;
   Prime Ideal of OK
   Two element generators:
       [3, 0, 0]
       [4, 1, 0]
   > J;
   Prime Ideal of OK
   Two element generators:
       [5, 0, 0]
       [7, 1, 0]
   > b := ChineseRemainderTheorem(I, J, OK!a, OK!1);
   > b - a in I;
   > b - 1 in J;
   > K!b;
The element found by the Chinese Remainder Theorem algorithm in this case is $ -4$.

The following lemma is a nice application of the Chinese Remainder Theorem. We will use it to prove that every ideal of $ \O _K$ can be generated by two elements. Suppose $ I$ is a nonzero integral ideals of $ \O _K$. If $ a\in I$, then $ (a)\subset I$, so $ I$ divides $ (a)$ and the quotient $ (a)/I$ is an integral ideal. The following lemma asserts that $ (a)$ can be chosen so the quotient $ (a)/I$ is coprime to any given ideal.

Lemma 9.1.6   If $ I,J$ are nonzero integral ideals in $ \O _K$, then there exists an $ a\in I$ such that $ (a)/I$ is coprime to $ J$.

Proof. Let $ \mathfrak{p}_1,\ldots, \mathfrak{p}_r$ be the prime divisors of $ J$. For each $ n$, let $ v_n$ be the largest power of $ \mathfrak{p}_n$ that divides $ I$. Choose an element $ a_n\in \mathfrak{p}_n^{v_n}$ that is not in $ \mathfrak{p}_n^{v_n+1}$ (there is such an element since $ \mathfrak{p}_n^{v_n}\neq \mathfrak{p}_n^{v_n+1}$, by unique factorization). By Theorem 9.1.3, there exists $ a\in\O _K$ such that

$\displaystyle a \equiv a_n \pmod{\mathfrak{p}_n^{v_n+1}}

for all $ n=1,\ldots, r$ and also

$\displaystyle a \equiv 0 \pmod{I/\prod \mathfrak{p}_n^{v_n}}.

(We are applying the theorem with the coprime integral ideals $ \mathfrak{p}_n^{v_n+1}$, for $ n=1,\ldots, r$ and the integral ideal $ I/\prod \mathfrak{p}_n^{v_n}$.)

To complete the proof we must show that $ (a)/I$ is not divisible by any $ \mathfrak{p}_n$, or equivalently, that the $ \mathfrak{p}_n^{v_n}$ exactly divides $ (a)$. Because $ a\equiv a_n \pmod{\mathfrak{p}_n^{v_n+1}}$, there is $ b \in \mathfrak{p}_n^{v_n+1}$ such that $ a = a_n + b$. Since $ a_n\in \mathfrak{p}_n^{v_n}$, it follows that $ a\in \mathfrak{p}_n^{v_n}$, so $ \mathfrak{p}_n^{v_n}$ divides $ (a)$. If $ a\in \mathfrak{p}_n^{v_n+1}$, then $ a_n=a-b\in \mathfrak{p}_n^{v_n+1}$, a contradiction, so $ \mathfrak{p}_n^{v_n+1}$ does not divide $ (a)$, which completes the proof. $ \qedsymbol$

Suppose $ I$ is a nonzero ideal of $ \O _K$. As an abelian group $ \O _K$ is free of rank equal to the degree $ [K:\mathbf{Q}]$ of $ K$, and $ I$ is of finite index in $ \O _K$, so $ I$ can be generated as an abelian group, hence as an ideal, by $ [K:\mathbf{Q}]$ generators. The following proposition asserts something much better, namely that $ I$ can be generated as an ideal in $ \O _K$ by at most two elements.

Proposition 9.1.7   Suppose $ I$ is a fractional ideal in the ring $ \O _K$ of integers of a number field. Then there exist $ a,b\in{}K$ such that $ I=(a,b)$.

Proof. If $ I=(0)$, then $ I$ is generated by $ 1$ element and we are done. If $ I$ is not an integral ideal, then there is $ x\in K$ such that $ xI$ is an integral ideal, and the number of generators of $ xI$ is the same as the number of generators of $ I$, so we may assume that $ I$ is an integral ideal.

Let $ a$ be any nonzero element of the integral ideal $ I$. We will show that there is some $ b\in I$ such that $ I=(a,b)$. Let $ J=(b)$. By Lemma 9.1.6, there exists $ a\in I$ such that $ (a)/I$ is coprime to $ (b)$. The ideal $ (a,b)=(a)+(b)$ is the greatest common divisor of $ (a)$ and $ (b)$, so $ I$ divides $ (a,b)$, since $ I$ divides both $ (a)$ and $ (b)$. Suppose $ \mathfrak{p}^n$ is a prime power that divides $ (a,b)$, so $ \mathfrak{p}^n$ divides both $ (a)$ and $ (b)$. Because $ (a)/I$ and $ (b)$ are coprime and $ \mathfrak{p}^n$ divides $ (b)$, we see that $ \mathfrak{p}^n$ does not divide $ (a)/I$, so $ \mathfrak{p}^n$ must divide $ I$. Thus $ (a,b)$ divides $ I$, so $ (a,b)=I$ as claimed. $ \qedsymbol$

We can also use Theorem 9.1.3 to determine the $ \O _K$-module structure of the successive quotients $ \mathfrak{p}^n/\mathfrak{p}^{n+1}$.

Proposition 9.1.8   Let $ \mathfrak{p}$ be a nonzero prime ideal of $ \O _K$, and let $ n\geq 0$ be an integer. Then $ \mathfrak{p}^n/\mathfrak{p}^{n+1} \cong \O _K/\mathfrak{p}$ as $ \O _K$-modules.

Proof. (Compare page 13 of Swinnerton-Dyer.) Since $ \mathfrak{p}^n\neq \mathfrak{p}^{n+1}$ (by unique factorization), we can fix an element $ b\in
\mathfrak{p}^n$ such that $ b\not\in \mathfrak{p}^{n+1}$. Let $ \varphi :\O _K\to\mathfrak{p}^n/\mathfrak{p}^{n+1}$ be the $ \O _K$-module morphism defined by $ \varphi (a)=ab$. The kernel of $ \varphi $ is $ \mathfrak{p}$ since clearly $ \varphi (\mathfrak{p})=0$ and if $ \varphi (a)=0$ then $ ab\in\mathfrak{p}^{n+1}$, so $ \mathfrak{p}^{n+1}\mid (a)(b)$, so $ \mathfrak{p}\mid (a)$, since $ \mathfrak{p}^{n+1}$ does not divide $ (b)$. Thus $ \varphi $ induces an injective $ \O _K$-module homomorphism $ \O _K/\mathfrak{p}\hookrightarrow \mathfrak{p}^{n}/\mathfrak{p}^{n+1}$.

It remains to show that $ \varphi $ is surjective, and this is where we will use Theorem 9.1.3. Suppose $ c\in \mathfrak{p}^{n}$. By Theorem 9.1.3 there exists $ d\in \O _K$ such that

$\displaystyle d \equiv c\pmod{\mathfrak{p}^{n+1}}$   and$\displaystyle \qquad
d \equiv 0\pmod{(b)/\mathfrak{p}^{n}}.

We have $ \mathfrak{p}^n\mid (c)$ since $ c\in\mathfrak{p}^n$ and $ (b)/\mathfrak{p}^n\mid (d)$ by the second displayed condition, so $ (b)=\mathfrak{p}^n\cdot(b)/\mathfrak{p}^n\mid (d)$, hence $ d/b\in \O _K$. Finally

$\displaystyle \varphi \left(\frac{d}{b}\right) \quad =\quad \frac{d}{b}\cdot b ...
\quad=\quad b\pmod{p^{n+1}} \quad=\quad c\pmod{p^{n+1}},

so $ \varphi $ is surjective. $ \qedsymbol$

William Stein 2004-05-06