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

$$\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

$$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

$$\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

$$\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

$$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;
   true
   > b - 1 in J;
   true
   > K!b;
   -4

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

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

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

$$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

$$d \equiv c\pmod{\mathfrak{p}^{n+1}}$$   and$$\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

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

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