Chinese Remainder Theorem in Several Scenarios of Ring Theory

Introduction

The classic version of Chinese remainder theorem tells us that we can find solutions out of modulus relations. You may have seen this poem when you were young.

有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

Translation:

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?

This poem can be translated into finding the solution of an equation:

$$\begin{cases} x \equiv 2 \pmod 3, \\ x \equiv 3 \pmod 5, \\ x \equiv 2 \pmod 7. \end{cases}$$

In modern language, we consider the integer ring $\mathbb{Z}$ (Z for Zahlen in German). Ideals $(3)$, $(5)$ and $(7)$ are pairwise coprime (or comaximal), and as a result, the map

$$\begin{aligned} \mathbb{Z} &\to \mathbb{Z}/(3) \times \mathbb{Z}/(5) \times \mathbb{Z}/(7) \\ n &\mapsto (n +(3), n +(5), n +(7)) \end{aligned}$$

is considered. The poem is all about finding a solution to the pre-image of $(2 +(3), 3+(5), 2+ (7))$. The Chinese remainder theorem tells us that, the map is surjective. Actually $233$ is such an element.

Nevertheless, what really matters here is about rings and ideals. That is why we try revisit the Chinese Remainder theorem in the language of ring theories. Although the importance of the classic version should never been ignored, we should also see it further.

We will study the Chinese remainder theorem in a ring, assuming the ring is commutative or assume something much weaker. We will also see a special case in Dedekind domains. We try our best to make assumptions as few as possible.

Chinese Remainder Theorem

We want to apply restrictions as little as possible. Let $A$ be a ring that is not necessarily commutative and does not necessarily contain a unit. A lot of things developed in ring theory will fail here, but we can still consider direct product of rings and coprime (or comaximal) ideals. Two ideals $\mathfrak{a}$ and $\mathfrak{b}$ of $A$ are coprime if $\mathfrak{a}+\mathfrak{b}=A$. We will do the Chinese remainder theorem on two levels of abstraction. Throughout, when discussing ideals, we are all talking about two-sided ideals.

Level 1 - Ring with Unity

When the ring has a unit, we have an easy view of the intersection and product of ideals

Proposition 1. Let $A$ be a ring with unity, $\mathfrak{a}$ and $\mathfrak{b}$ two ideals of $A$. If $\mathfrak{a}$ and $\mathfrak{b}$ are coprime, i.e. $\mathfrak{a}+\mathfrak{b}=A$, then

$$\mathfrak{a} \cap \mathfrak{b}=\mathfrak{ab}+\mathfrak{ba}.$$

In particular, when $A$ is commutative, one always has $\mathfrak{a} \cap \mathfrak{b} = \mathfrak{ab}$.

Proof. The last statement follows from the relation that $\mathfrak{ab}=\mathfrak{ba}$, therefore it suffices to prove the first relation. Notice that there exists $x \in \mathfrak{a}$ and $y \in \mathfrak{b}$ such that $x+y=1$. As a result, for any $a \in \mathfrak{a} \cap \mathfrak{b}$, one has

$$a=a(x+y)=ax+ay \in \mathfrak{ba}+\mathfrak{ab} \implies \mathfrak{a} \cap \mathfrak{b} \subset \mathfrak{ba}+\mathfrak{ab}.$$

Conversely, since both $\mathfrak{a}$ and $\mathfrak{b}$ are two-sided ideals, we see $\mathfrak{ab} \subset \mathfrak{a} \cap \mathfrak{b}$ and $\mathfrak{ba} \subset \mathfrak{a} \cap \mathfrak{b}$, so is their sum. $\square$

Let $A$ be a ring with unity. Consider a finite number of ideals $\mathfrak{a}_1,\dots,\mathfrak{a}_n$. Define a homomorphism

$$\begin{aligned} \phi:A &\to \prod_{i=1}^{n}(A/\mathfrak{a}_i), \\ x &\mapsto (x+\mathfrak{a}_1, \dots, x+\mathfrak{a}_n). \end{aligned}$$

We do not assume that these $\mathfrak{a}_i$ are pairwise coprime just yet. We will see what happens when they are.

Theorem 1. For the homomorphism $\phi$ defined above,

1. $\phi$ is injective if and only if $\bigcap_{i=1}^{n}\mathfrak{a}_i=(0)$.
2. If the $\mathfrak{a}_i$ are pairwise coprime and $A$ is commutative, then $\prod_{i=1}^{n}\mathfrak{a}_i=\bigcap_{i=1}^{n}\mathfrak{a}_i$.
3. $\phi$ is surjective if and only if the $\mathfrak{a}_i$ are pairwise coprime.

Proof. The first statement follows from the fact that $\ker\phi=\bigcap_{i=1}^{n}\mathfrak{a}_i=(0)$.

For the second statement, according to proposition 1, this equality holds for $n=2$. Now suppose that $n>2$ and this statement holds for $\mathfrak{a}_1,\dots,\mathfrak{a}_{n-1}$. Let $\mathfrak{b}=\prod_{i=1}^{n-1}\mathfrak{a}_i=\bigcap_{i=1}^{n-1}\mathfrak{a}_i$, then we will show that $\mathfrak{a}_n+\mathfrak{b}=A$ and therefore

$$\mathfrak{b}\mathfrak{a}_n=\prod_{i=1}^{n}\mathfrak{a}_i=\mathfrak{b} \cap \mathfrak{a}_n = \bigcap_{i=1}^{n}\mathfrak{a}_i.$$

Notice that $\mathfrak{a}_i$ and $\mathfrak{a}_n$ are pairwise coprime for all $1 \le i \le n-1$. Therefore, in particular, for each of these $i$, we have equation $x_i+y_i =1$ where $x_i \in \mathfrak{a}_i$ and $y_i \in \mathfrak{b}_i$. Here we use the fact that $1 \in A$. Commutativity of $A$ is also used because proposition 1 shows us that without commutativity we cannot even prove it for $n=2$.

From this equation we deduce that

$$\prod_{i=1}^{n-1}x_i = \prod_{i=1}^{n-1}(1-y_i).$$

Expanding the product on the right hand side, we see $\prod_{i=1}^{n-1}(1-y_i)=\prod_{i=1}^{n-1}x_i \equiv 1 \pmod{\mathfrak{a}_n}$. This implies that there exists $y \in \mathfrak{a}_n$ such that $\prod_{i=1}^{n-1}x_i+y=1$. Since $\prod_{i=1}^{n-1}x_i \in \mathfrak{b}$, we have shown that $\mathfrak{a}_n+\mathfrak{b}=A$.

For the third statement, we first assume that $\phi$ is surjective. It suffices to show, for example, $\mathfrak{a}_1$ and $\mathfrak{a}_2$ are coprime. There exists $x \in A$ such that $\phi(x)=(1+\mathfrak{a}_1,0+\mathfrak{a}_2,\dots,0+\mathfrak{a}_n)$. This shows us that $x \in \mathfrak{a}_2$ and $1-x \in \mathfrak{a}_1$. As a result,

$$1=(1-x)+x \in \mathfrak{a}_1+\mathfrak{a}_2,$$

hence these two ideals are coprime. This procedure applies to all other $\mathfrak{a}_i$ by merely modifying the index.

Conversely, assume the $\mathfrak{a}_i$ are pairwise coprime, then it suffices to show that there exists $x \in A$ such that $\phi(x)=(1+\mathfrak{a}_1,0+\mathfrak{a}_2,\dots,0+\mathfrak{a}_n)$ because we can apply the same procedure to all other $i$th component and $1$ can be then replaced with any other element $a$ of $A$ (for example, for this case, we replace $x$ with $ax$). All other cases can be generated by addition.

Since $\mathfrak{a}_1+\mathfrak{a}_i=(1)$ for all $i>1$, we have $u_i+v_i = 1$ where $u_i \in \mathfrak{a}_1$ and $v_i \in \mathfrak{a}_i$. Take

$$x=\prod_{i=2}^{n}v_i = \prod_{i=2}^{n}(1-u_i),$$

then we see $x \equiv 0 \pmod{\mathfrak{a}_i}$ for all $i>1$ but $x \equiv 1 \pmod{\mathfrak{a}_1}$. This $x$ will be mapped to $(1+\mathfrak{a}_1,0+\mathfrak{a}_2,\dots,0+\mathfrak{a}_n)$ as expected. $\square$

It also matters that ideals are two-sided, otherwise these products of $n-1$ terms will make less sense.

Corollary 1 (Chinese Remainder Theorem). If the $\mathfrak{a}_i$ are pairwise coprime, then $\phi$ is an isomorphism:

$$\frac{A}{\bigcap_{i=1}^{n}\mathfrak{a}_i} \cong \prod_{i=1}^{n}\frac{A}{\mathfrak{a}_i}.$$

If $A$ is commutative, then

$$\frac{A}{\prod_{i=1}^{n}\mathfrak{a}_i} \cong \prod_{i=1}^{n}\frac{A}{\mathfrak{a}_i}$$

Level 2 - Noncommutative Ring without Unity

We first need a clarification of what do we mean by “noncommutative ring”. When we say “let $A$ be a noncommutative ring”, we mean $A$ is not necessarily commutative (it can be but we do not care); when we say “$A$ is noncommutative”, we mean $A$ is not commutative. This is a matter of convenience.

What hurts most on this level is that we cannot use unity anymore this time (there can be a unit, but we should not care here). To work around this, we need to figure out what we essentially did when proving the surjectivity of $\phi$ in theorem 1. We find a suitable element in the first ideal, and a suitable element in the intersection of all other ideals.

For this reason, we replace being pairwise coprime with a different condition. It is easy to see that if all the ideals are pairwise coprime, then the following condition will be satisfied automatically.

Theorem 2 (Chinese Remainder Theorem). Let $A$ be a noncommutative ring, let $\mathfrak{a}_1,\dots,\mathfrak{a}_n$ be ideals such that

$$\mathfrak{a}_i+\bigcap_{1 \le j \le n}^{j \ne i}\mathfrak{a}_j = A,$$

for all $i=1,2,\dots,n$, then one has an isomorphism

$$\frac{A}{\bigcap_{i=1}^{n}\mathfrak{a}_i} \cong \prod_{i=1}^{n}\frac{A}{\mathfrak{a}_i},$$

induced by the map

$$\begin{aligned} \phi:A &\to \prod_{i=1}^{n}\frac{A}{\mathfrak{a}_i} \\ x &\mapsto (x+\mathfrak{a}_1,\dots,x+\mathfrak{a}_n). \end{aligned}$$

Proof. We have $\ker\phi=\bigcap_{i=1}^{n}\mathfrak{a}_i$. Therefore it remains to show that our improved coprime condition implies that $\phi$ is surjective. Again, it suffices to show that the preimage of $(a+\mathfrak{a}_1,0+\mathfrak{a}_2,\dots,0+\mathfrak{a}_n)$ exists for all $r \in A$ (wait! One should not consider $1$ here!). Since $\mathfrak{a}_1+\bigcap_{i=2}^{n}\mathfrak{a}_i=A$, for any $a \in A$, there exists $a_1 \in \mathfrak{a}_1$ and $a_2 \in \bigcap_{i=1}^{n}\mathfrak{a}_2$ such that

$$a=a_1+a_2.$$

As a result,

$$\begin{aligned} \phi(a_2)&=(a_2+\mathfrak{a}_1,a_2+\mathfrak{a}_2,\dots,a_2+\mathfrak{a}_n) \\ &=(a_1+a_2+\mathfrak{a}_1,0+\mathfrak{a}_2,\dots,0+\mathfrak{a}_n) \\ &=(a+\mathfrak{a}_1,0+\mathfrak{a}_2,\dots,0+\mathfrak{a}_n) \\ \end{aligned}$$

This proves the surjectivity of $\phi$. $\square$

Bonuses

We

Theorem 3 (Chinese Remainder Theorem). Let $A$ be a ring, let $\mathfrak{a}_1,\dots,\mathfrak{a}_n$ be let $\mathfrak{a}_1,\dots,\mathfrak{a}_n$ be ideals of $A$. If all the $\mathfrak{a}_i$ are pairwise coprime and for all $i$,

$$A=\mathfrak{a}_i+A^2.$$

then Chinese remainder theorem holds.

If $A$ has a unit, then the condition $A=\mathfrak{a}_i+A^2$ is automatically satisfied.

Proof. Assume first all the $\mathfrak{a}_i$ are coprime and satisfy $A=\mathfrak{a}_i+A^2$. It suffices to prove the case when $i=1$. Notice that

$$\begin{aligned} A=\mathfrak{a}_1+A^2 &= \mathfrak{a}_1+(\mathfrak{a}_1+\mathfrak{a}_2)(\mathfrak{a}_1+\mathfrak{a}_3) \\ &= \mathfrak{a}_1 + \mathfrak{a}_1^2 +\mathfrak{a}_2\mathfrak{a}_1+\mathfrak{a}_1\mathfrak{a}_3+\mathfrak{a}_2\mathfrak{a}_3 \\ &\subset \mathfrak{a}_1 + \mathfrak{a}_2\mathfrak{a}_3 \\ &\subset \mathfrak{a}_1 + \mathfrak{a}_2 \cap \mathfrak{a}_3 \\ &\subset A. \end{aligned}$$

Therefore $A=\mathfrak{a}_1 + \mathfrak{a}_2 \cap \mathfrak{a}_3$. Suppose now $3<m < n$ and

$$A = \mathfrak{a}_1 + \mathfrak{a}_2 \cap \mathfrak{a}_3 \cap \dots \cap \mathfrak{a}_m,$$

then

$$\begin{aligned} A = \mathfrak{a}_1 + A^2 & = \mathfrak{a}_1 + (\mathfrak{a}_1 + \mathfrak{a}_2 \cap \mathfrak{a}_3 \cap \dots \cap \mathfrak{a}_m)(\mathfrak{a}_1+\mathfrak{a}_{m+1}) \\ & = \mathfrak{a}_1+\mathfrak{a}_1^2 +\mathfrak{a}_1\mathfrak{a}_{m+1}+(\mathfrak{a}_2 \cap \mathfrak{a}_3 \cap \dots \cap \mathfrak{a}_m)\mathfrak{a}_1 + (\mathfrak{a}_2 \cap \mathfrak{a}_3 \cap \dots \cap \mathfrak{a}_m)\mathfrak{a}_{m+1} \\ & \subset \mathfrak{a}_1 + \mathfrak{a}_2 \cap \mathfrak{a}_3 \cap \dots \cap \mathfrak{a}_m \cap \mathfrak{a}_{m+1} \\ &\subset A. \end{aligned}$$

By induction we have $\mathfrak{a}_1+\bigcap_{j=2}^{n}\mathfrak{a}_j = A$ as desired. The next follows from theorem 2. $\square$

Finally we offer an interesting version of Chinese remainder theorem, involving Dedekind domains.

Theorem 4 (Chinese Remainder Theorem). Let $\mathfrak{a}_1,\dots,\mathfrak{a}_n$ be ideals and let $x_1,\dots,x_n$ be elements in a Dedekind domain $A$. Then the system of congruences $x\equiv x_i \pmod{\mathfrak{a}_i}$ ($1 \le i \le n$) has a solution $x$ in $A$ if and only if $x_i \equiv x_j \pmod{\mathfrak{a}_i+\mathfrak{a}_j}$ whenver $i \ne j$.

Proof. Define $\phi:A \to \bigoplus_{i=1}^{n}A/\mathfrak{a}_i$ by $x \mapsto (x+\mathfrak{a}_1,\dots,x+\mathfrak{a}_n)$ and $\psi: \bigoplus_{i=1}^{n}A/\mathfrak{a}_i \to \bigoplus_{i<j}A/(\mathfrak{a}_i+\mathfrak{a}_j)$ such that the $(i,j)$-component of $\psi(x_1+\mathfrak{a}_1,\dots,x_n+\mathfrak{a}_n)$ is $x_i-x_j+\mathfrak{a}_i+\mathfrak{a}_j$, then the statement is equivalent to saying that the sequence of $A$-modules

$$A \xrightarrow{\phi}\bigoplus_{i=1}^{n}A/\mathfrak{a}_i \xrightarrow{\psi}\bigoplus_{i<j}A/(\mathfrak{a}_i+\mathfrak{a}_j)$$

is exact. It is clear that $\operatorname{im}\phi \subset \ker \psi$. We need to show the converse. Since exactness is a local property, we can assume that $A$ is a discrete valuation ring, meaning that there is an element $x \in A$ such that all ideals $\mathfrak{a}$ are of the form $(x^k)$. Therefore we can rearrange the $\mathfrak{a}_i$ so that $\mathfrak{a}_1 = (x^{k_1}) \supset \mathfrak{a}_2=(x^{k_2}) \supset \cdots \supset \mathfrak{a}_n=(x^{k_n})$. In this case, one has $k_1 \le k_2 \le \dots \le k_n$. In this case, we have $\mathfrak{a}_i+\mathfrak{a}_j=\mathfrak{a}_i$ whenever $i<j$.

Now pick $(x_1+\mathfrak{a}_1,\dots,x_n+\mathfrak{a}_n)\in \ker\psi$, then $x_i-x_j \in \mathfrak{a}_i+\mathfrak{a}_j=\mathfrak{a}_i$. Therefore $x_i \equiv x_j \pmod{\mathfrak{a}_i}$. In particular, taking $j=n$, we see

$$\phi(x_n)=(x_n+\mathfrak{a}_1,\dots,x_n+\mathfrak{a}_n)=(x_1+\mathfrak{a}_1,\dots,x_n+\mathfrak{a}_n) \implies (x_1+\mathfrak{a}_1,\dots,x_n+\mathfrak{a}_n)\in \operatorname{im}\phi,$$

as is wanted. $\square$

Examples and Remarks

If we replace $A$ with $\mathbb{Z}$ and the $\mathfrak{a}_i$ with ideals generated by coprime numbers, then we reach the classic version of the Chinese remainder theorem.

For non-commutative case, the reader can read this post

For another example, we consider the Lagrange interpolation, which is the special case of the Chinese Remainder theorem on the ring $\mathbb{R}[X]$ with extra consideration on evaluations. As you may guess, $\mathbb{R}$ can be replaced with other fields.

Find a polynomial $f(X) \in \mathbb{R}[X]$ passing three points $(1,2)$, $(2,-1)$ and $(3,2)$.

Consider ideals $\mathfrak{a}_1=(x-1)$, $\mathfrak{a}_2=(x-2)$ and $\mathfrak{a}_3=(3,2)$. Then, for example, $f(X) \equiv f_1(X) \pmod{\mathfrak{a}_1}$, where $f_1$ is a real polynomial that attains $2$ at the point $1$. The Chinese Remainder theorem tells us that such $f$ exists. This approach is seemingly an unnecessary overkill but it allows us to view a theorem in numerical analysis in an algebraic way.

We can also make things that are not related to polynomial rings a matter of polynomial rings. For example, via Chinese Remainder Theorem, we can compute $\mathbb{C} \otimes_\mathbb{R} \mathbb{C}$ in the following way:

$$\begin{aligned} \mathbb{C} \otimes_\mathbb{R} \mathbb{C} &\cong \mathbb{C} \otimes_\mathbb{R} \mathbb{R}[X]/(X^2+1) \\ &\cong (\mathbb{C} \otimes \mathbb{R}[X])/(X^2+1) \\ &\cong\mathbb{C}[X]/(X^2+1) \\ &\cong\mathbb{C}[X]/(X-i)(X+i) \\ &\cong\mathbb{C}[X]/(X-i) \times \mathbb{C}[X]/(X+i) \\ &\cong \mathbb{C} \times \mathbb{C} \end{aligned}$$

There is a proof of Hilbert’s theorem 90 (of cyclic extensions) where the isomorphism above is used, with degrees higher than $2$: https://mathoverflow.net/a/21117/172944

Our last remark shows the geometrical interpretation of Chinese Remainder Theorem. In geometry, we consider the spectrum of a unitary commutative ring, which gives rise to an affine scheme. If $A=\prod_{i=1}^{n}A_i$ is a direct product of such rings $A_i$, then $\operatorname{Spec}A \cong \coprod_{i=1}^{n}\operatorname{Spec}(A_i)$. Conversely, using Chinese remainder theorem, we can show that if $\operatorname{Spec}A$ is a disjoint union of two spectrums, then $A$ is a direct product of two other rings. To be precise:

Let $A$ be a unitary commutative ring, then the following statements are equivalent:

1. $X=\operatorname{Spec}(A)$ is disconnected.
2. $A=A_1 \times A_2$ where neither of the two rings is a zero ring.
3. There is an element $e \ne 0,1$ such that $e^2=e$, i.e. an idempotent element.

In particular, since in a local ring any idempotent element is $0$ or $1$, we see the spectrum of it has to be connected.

References

• Michael Atiyah, I.G. MacDonald, Introduction to Commutative Algebra

• Ravi Vakil, Foundations of Algebraic Geometry