Chinese Mathematics

In this post, we use the notion of ideals to prove the Chinese remainder theorem.

Theorem 1 (Chinese Remainder Theorem). Let $a,b,m,n$ be integers. If $\gcd(m, n) = 1$ , then there exists a unique integer $0 \leq x < mn$ such that

$x \equiv_m a,\quad x \equiv_n b.$

Problem 1. Given rings $R, S$ , define the operations $+, \cdot$ pointwise:

$\begin{aligned} (r_1, s_1) + (r_2, s_2) &:= (r_1 + r_2, s_1 + s_2), \\ (r_1, s_1) \cdot (r_2, s_2) &:= (r_1 \cdot r_2, s_1 \cdot s_2). \end{aligned}$

Show that

$R \oplus S := \{(r,s) : r \in R, s \in S\}$

forms a ring. More generally, inductively define

$\displaystyle \bigoplus_{i=1}^n R_i := \bigoplus_{i=1}^{n-1} R_i \oplus R_n.$

Solution. Straightforward verification of ring axioms.

Let $R$ be a ring and $I, J \subseteq R$ be ideals.

Problem 2. Show that the map $\phi : R \to R/I \oplus R/J$ defined by

$\phi(x) := (x + I, x+ J)$

is a well-defined ring homomorphism. Evaluate $\ker(\phi)$ .

(Click for Solution)

Solution. Since $I, J$ are ideals, the quotient sets $R/I, R/J$ have natural ring structures. By Problem 1, the product $R/I \times R/J$ has a natural ring structure, and

$\begin{aligned} \phi(x \cdot y ) &= ((x \cdot y) + I, (x \cdot y) + J) \\ &= ((x + I) \cdot (y + I), (x+J) \cdot (y+J)) \\ &= (x+ I, x_J) \cdot (y + I, y + J) \\ &= \phi(x) \cdot \phi(y). \end{aligned}$

Replace $\cdot$ with $+$ to conclude that $\phi$ is a ring homomorphism.

To evaluate $\ker(\phi)$ , fix $u \in \ker(\phi)$ so that

$\phi(u) = (u + I, u + J) = (I, J).$

Then $u \in I$ and $u \in J$ , so that $u \in I \cap J$ . It is clear that $I \cap J \subseteq \ker(\phi)$ , so that $\ker(\phi) = I \cap J$ .

Problem 3. Fix $K \subseteq R$ . Show that there exists a unique ideal $\langle K \rangle \subseteq R$ such that

$\langle K \rangle$ contains $S$ , and
for any ideal $L \subseteq R$ that contains $S$ , $L$ contains $\langle K \rangle$ .

(Click for Solution)

Solution. Define

$\mathcal K:= \{L : L \subseteq R\ \text{ideal},\ S \subseteq L\}.$

It is clear that $R \in \mathcal K$ , so that $\mathcal K \neq \emptyset$ . Define $\langle K \rangle := \bigcap_{L \in \mathcal K} L$ . We claim that $(K)$ satisfies the desired properties.

To check that $\langle K \rangle$ is an ideal, we note that for any $x \in R$ and $z \in K$ and ideal $L \in \mathcal K$ , $xz \in L$ . Therefore, $xz \in \bigcap_{L \in \mathcal K}L = \langle K \rangle$ . The right-sided ideal property holds similarly. For the second claim, it is obvious that $\langle K \rangle = \bigcap_{L_0 \in \mathcal K} L_0 \subseteq L$ .

Define $I \cdot J := \langle \{xy : x \in I, y \in J\} \rangle$ .

Problem 4. Show that

$\displaystyle I \cdot J = \left\{ \sum_{k=1}^n x_k y_k : n \in \mathbb N, x_k \in I, y_k \in J \right\}.$

Deduce that $I \cdot J \subseteq I \cap J$ .

(Click for Solution)

Solution. For the first claim, the direction $(\supseteq)$ is trivial.

For the direction $(\subseteq)$ , since the set

$\displaystyle K := \left\{ \sum_{k=1}^n x_k y_k : n \in \mathbb N, x_k \in I, y_k \in J \right\} \subseteq R$

contains the set $\{xy : x \in I, y \in J\}$ , by Problem 3, it suffices to check that it is an ideal. Fix $w \in R$ and $z \in K$ . Write

$\displaystyle z = \sum_{k=1}^n x_k y_k.$

Since $I$ is an ideal, $wx_k \in I$ for each $k$ , so that

$\displaystyle wz = w \left( \sum_{k=1}^n x_k y_k \right) = \sum_{k=1}^n wx_k \cdot y_k \in K.$

The right-sided ideal property holds similarly. Therefore, $K$ is an ideal, as required. For the second claim, each $x_k y_k \in I \cap J$ , and since the latter is an ideal, the result follows.

Problem 5. Given that $I + J = R$ , show that the map $\phi$ defined in Problem 2 is surjective. If furthermore that:

$R$ is commutative, and
$1 \in R$ ,

show that $R/(I \cdot J) \cong R/ I \oplus R/ J$ .

(Click for Solution)

Solution. Fix $(x + I, y + J) \in R/ I \oplus R/ J$ .

We need to cook up $z \in R$ such that $z - x \in I$ and $z - y \in J$ , so that

$\phi(z) = (z + I , z + J) = (x + I, y + J).$

Since $I + J = R$ and $x - y \in R$ , there exists $u \in I, v \in J$ such that

$x - y = u + v \quad \Rightarrow \quad x + (-u) = y + v.$

Define

$z := x + (-u) = y+v.$

Then $z-x = -u \in I$ and $z - y = v \in J$ , as required.

By Problem 4, $I \cdot J \subseteq I \cap J$ . If $1 \in R$ , then find $x \in I$ and $y \in J$ such that $1 = x + y$ . Then for any $z \in I \cap J$ , $z \in J$ implies

$z = z \cdot 1 = zx + zy = xz + zy \in I \cdot J,$

and the first isomorphism theorem for rings yields

$R/(I \cdot J) \cong R/ I \oplus R/ J.$

Given ideals $I_1,\dots, I_k \subseteq R$ , inductively define

$\displaystyle \prod_{j=1}^n I_j := \prod_{j=1}^{n-1} I_j \cdot I_n.$

Furthermore suppose that $R$ is commutative and $1 \in R$ .

Problem 6. Given ideals $I_1,\dots, I_k$ , suppose $I_m + I_n = R$ for any $m \neq n$ . Prove that

$\displaystyle R/ \prod_{j=1}^k I_j \cong \bigoplus_{j=1}^k R/I_j.$

(Click for Solution)

Solution. We proceed by induction on $k \geq 2$ . The case $k = 2$ holds by Problem 5. For the general case, define $I := \prod_{j=1}^k I_j$ . The property $I_j + I_{k+1} = R$ implies that $I + I_{k+1} = R$ and hence, so that by the $k =2$ case and the induction hypothesis,

$\begin{aligned} R/ \prod_{j=1}^{k+1} I_j &\cong R/(I \cdot I_{k+1}) \\ &\cong R/I \oplus R/I_{k+1} \\ &\cong \bigoplus_{j=1}^k R/I_j \oplus R/I_{k+1}\\ &\cong \bigoplus_{j=1}^{k+1} R/I_j.\end{aligned}$

Problem 7. Deduce the generalised Chinese remainder theorem: given integers $a_1,a_2\dots, a_k$ and $n_1,n_2,\dots, n_k$ such that

$i \neq j \quad \Rightarrow \quad \gcd(n_i, n_j) = 1,$

there exists a unique integer $0 \leq x < n_1 n_2 \cdot \dots \cdot n_k$ such that

$x \equiv_{n_i} a_i,\quad 1 \leq i \leq k.$

(Click for Solution)

Solution. It is obvious that $\mathbb Z$ is a commutative ring with $1$ . Recall that for each $j$ , $n_j \mathbb Z \subseteq \mathbb Z$ as an ideal. Given $i \neq j$ , since $\gcd(n_i, n_j) = 1$ , use Bézout’s lemma to produce integers $r, s$ such that