Chinese remainder theorem

Section 2.9 Chinese remainder theorem

Subsection 2.9.1 Chinese remainder theorem: general form

In its general form, the Chinese remainder theorem (CRT) articulates conditions for which a given ring can be expressed (up to isomorphism) as a direct product of rings. The result is a pervasive and useful tool in ring theory, often employed to prove some property of a given ring \(R\) by exhibiting an isomorphism between \(R\) and a product ring \(\prod_{k=1}^n S_k\text{,}\) and proving a similar result for the (often simpler rings) \(S_k\text{,}\) and then using the simple structure of product rings to lift the result back to \(R\text{.}\)

🔗

The specific conditions laid out by the CRT involve quotients of rings by pairwise coprime ideals.

🔗

Definition 2.9.1. Coprime ideals.

Let \(R\) be a nonzero commutative ring. Ideals \(I\) and \(J\) of \(R\) are coprime if \(I+J=R\text{.}\) Equivalently, \(I\) and \(J\) are coprime if we can write \(1=i+j\) for some \(i\in I\) and \(j\in J\text{.}\)

🔗

Theorem 2.9.2. Chinese remainder theorem (CRT).

Let \(R\) be a commutative ring, and let \(I_1, I_2, \dots, I_n\) be ideals of \(R\text{.}\) For all \(1\leq k\leq n\text{,}\) we let \(\pi_k\colon R\rightarrow R/I_k\) be the quotient map, and we define

\begin{align*} \phi\colon R \amp \rightarrow \prod_{k=1}^n R/I_k\\ r \amp \mapsto (\pi_1(r), \pi_2(r),\dots, \pi_n(r)) \text{.} \end{align*}

\(\phi\) is a ring homomorphism with kernel

\begin{align*} \ker\phi \amp =\bigcap_{k=1}^n I_k\text{.} \end{align*}

🔗

🔗
\(\phi\) is surjective if and only if the ideals \(I_k\) are pairwise coprime: i.e., \(I_j+I_k=R\) for all \(j\ne k\text{.}\)
🔗

🔗
If the ideals \(I_k\) are pairwise coprime, then

\begin{align*} \bigcap_{k=1}^n I_k \amp =\prod_{k=1}^n I_k\text{,} \end{align*}

and we have

\begin{align*} R/\prod_{k=1}^n I_k \amp \cong \prod_{k=1}^n R/I_k\text{.} \end{align*}

🔗

🔗

🔗

Proof.

That \(\phi\) is a ring homomorphism follows easily from the ring structure on \(\prod_{k=1}^n R/I_k\text{.}\) As for the statement about the kernel, we have

\begin{align*} \ker\phi \amp = \bigcap_{k=1}^n\ker \pi_k\\ \amp =\bigcap_{k=1}^n I_k\text{.} \end{align*}

🔗

🔗
For each \(1\keq k\leq n\text{,}\) let \(e_k=(a_i)_{i=1}^n\) be defined as

\begin{align*} a_i \amp =\begin{cases} 1 \amp \text{if } i=k\\ 0 \amp \text{if } i\ne k \text{.}\end{cases} \end{align*}

It is not difficult to see that \(\phi\) is surjective if and only if for each \(k\) there is some \(r_k\in R\) such that \(\phi(r_k)=e_k\text{.}\) Indeed, the forward implication is obvious, and the reverse follows from the fact that given any \((a_1+I_1,a_2+I_2,\dots, a_n+I_n)\in \prod_{k=1}^nR/I_k\text{,}\) we have

\begin{align*} \phi(\sum_{k=1}^na_kr_k) \amp =\sum_{k=1}^n\phi(a_k)\phi(r_k)\\ \amp = \sum_{k=1}\phi(a_k)e_k\\ \amp =(a_1+I_1, a_2+I_2,\dots, a_n+I_n)\text{.} \end{align*}

Thus it suffices to show that we can find \(r_k\) satisfying \(\phi(r_k)=e_k\) if and only if the ideals \(I_k\) are pairwise coprime.

🔗

Assume for all \(k\) there exist \(r_k\in R\) satisfying \(\phi(r_k)=e_k\text{.}\) For ideals \(I_j\) and \(I_k\text{,}\) \(j\ne k\text{,}\) since \(\phi(r_k)=e_k\text{,}\) we have, by definition of \(\phi\text{,}\)

\begin{align} r_k \amp = 1+i_k \amp \tag{2.9.1}\\ r_k \amp =0+i_j \tag{2.9.2} \end{align}

for elements \(i_k\in I_k\) and \(i_j\in I_j\text{.}\) But then

\begin{align*} 1 \amp =r_k-i_k=i_j-i_k\in I_j+I_k\text{,} \end{align*}

showing that \(I_j\) and \(I_k\) are coprime.

🔗

Now assume that the ideals \(I_k\) are pairwise coprime. Fix \(1\leq k \leq n\text{.}\) For any \(j\ne k\text{,}\) since \(I_k+I_j=R\text{,}\) we can find elements \(i_j\in I_j\) and \(i_{k,j}\in I_k\) such that \(i_j=1-i_{k,j}\text{.}\) Let

\begin{align*} r_k \amp =\prod_{j\ne k} i_j=\prod_{k=1}(1-i_{k,j})\text{.} \end{align*}

Since \(i_j\in I_j\) for all \(j\ne k\text{,}\) we have

\begin{align*} r_k \amp =\prod_{j\ne k}i_j\in \bigcap_{j\ne k}I_j \end{align*}

and hence \(\pi_j(r_k)=0\) for all \(j\ne k\text{.}\)

🔗

Since \(1-i_{k,j}\in 1+I_k\) for all \(j\ne k\text{,}\) we have

\begin{align} \pi_k(r_k) \amp = \prod_{j\ne k}\pi_k(1-i_{k,j})\tag{2.9.3}\\ \amp = \prod_{j\ne K}(1+I_k)\tag{2.9.4}\\ \amp = 1\text{,}\tag{2.9.5} \end{align}

as desired.

🔗

🔗
From (1) and (2), it remains only to show that if the ideals \(I_k\) are pairwise coprime, then

\begin{align*} \prod_{j=1}^n I_j \amp = \bigcap_{j=1}^n I_j\text{.} \end{align*}

The inclusion \(\subseteq\) holds for any collection of ideals: we have seen this for \(n=2\text{,}\) and the result generalizes easy by induction. Let’s show that reverse inclusion under the additional assumption of coprimality.

🔗

🔗

🔗

Since a ring isomorphism \(\phi\colon R\rightarrow S\) restricts to an isomorphism between the unit groups \(R^*\) and \(S^*\text{,}\) and since for any product ring \(S=\prod_{i\in I}R_i\) we have \(S^*=\prod_{i\in i}R_i^*\text{,}\) we immediately obtain the following corollary.

🔗

Corollary 2.9.3. CRT for unit groups.

Let \(R\) be a commutative ring, let \(I_1, I_2, \dots, I_n\) be a collection of pairwise coprime ideals of \(R\text{,}\) and let

\begin{align*} I \amp =\bigcap_{k=1}^n I_k=\prod_{k=1}^n I_k\text{.} \end{align*}

The map

\begin{align} \phi\colon (R/I)^* \amp\rightarrow \prod_{k=1}^n (R/I_k)^* \tag{2.9.6}\\ r+I \amp \mapsto (r+I_1, r+I_2,\dots, r+I_n)\tag{2.9.7} \end{align}

is an isomorphism of groups.

🔗

Subsection 2.9.2 CRT in PIDs

In a PID we have an alternative formulation for when two ideals are coprime.

🔗

Proposition 2.9.4. Coprime prime ideals in PID.

Let \((a)\) and \((b)\) be ideals of the PID \(R\text{.}\) The following statements are equivalent.

\((a)\) and \((b)\) are coprime.
🔗

🔗
\(\displaystyle (a,b)=(1)\)
🔗

🔗
If \(c\in R\) satisfies \(c\mid a\) and \(c\mid b\text{,}\) then \(c\) is a unit.
🔗

🔗

🔗

In particular, in the case of integers, Proposition 2.9.4 tells that ideals \((a)\) and \((b)\) of \(\Z\) are coprime if and only if \(\gcd(a,b)=1\text{.}\) We immediately get the following special case of the CRT for integers. The last statement of Theorem 2.9.5 is simply a restatement of the first using the language of congruences. It is the classic form of the CRT encountered in courses in discrete mathematics or elementary number theory.

🔗

Theorem 2.9.5. CRT: integers.

Let \(a_1,a_2,\dots, a_n\) be pairwise relatively prime integers (i.e., \(\gcd(a_i, a_j)=1\) for all \(i\ne j\)), and let \(a=\prod_{k=1}^na_i\text{.}\)

The map

\begin{align*} \phi\colon \Z/a\Z \amp \rightarrow \prod_{k=1}^n \Z/a_k\Z\\ [m]_a \amp \mapsto ([m]_{a_1}, [m]_{a_2},\dots, [m]_{a_n}) \end{align*}

is an isomorphism of rings.

🔗

🔗
The map

\begin{align*} \phi\colon (\Z/a\Z)^* \amp \rightarrow \prod_{k=1}^n (\Z/a_k\Z)^*\\ [m]_a \amp \mapsto ([m]_{a_1}, [m]_{a_2},\dots, [m]_{a_n}) \end{align*}

is an isomorphism of groups.

🔗

🔗
For any choice of integers \(m_1, m_2, \dots, m_n\text{,}\) the set of \(x\) satisfying the system of congruences

\begin{align} x \amp \equiv m_1 \pmod{a_1}\tag{2.9.8}\\ x \amp \equiv m_2 \pmod{a_2}\tag{2.9.9}\\ \amp \vdots \tag{2.9.10}\\ x \amp \equiv m_n \pmod{a_n} \tag{2.9.11} \end{align}

forms a unique congruence class modulo \(a\text{.}\) That is, (i) there is a solution \(x\in \Z\) to this system of congruences, and (ii) \(y\) is another solution if and only if \(x\equiv y\pmod a\text{.}\)

🔗

🔗

🔗

Remark 2.9.6. CRT for integers.

In the special case of the CRT applied to integers, when asked to solve a system of congruences as in (2.9.8), it suffices to find one solution \(x\text{,}\) in which case the set of all solutions is \([x]_a\text{,}\) where \(a=a_1a_2\cdots a_n\text{.}\) Furthermore, we can use the division algorithm to find our solution \(x\) in a relatively low-cost manner. The steps below outline such a computational method.

For each \(k\text{,}\) compute \(M_k=\prod_{j\ne k}a_j\text{.}\)
🔗

🔗
For each \(k\) compute a multiplicative inverse \(c_k\) of \(M_k\) modulo \(a_k\text{:}\) i.e., find \(c_k\) satisfying \(c_kM_k\equiv 1 \pmod a_k\text{.}\) This can be done either by inspection (in simple cases) or by performing the Euclidean algorithm to find integers \(c,d\) satisfying \(cM_k+da_k=1\) (since \(\gcd(M_k, a_k)=1\)) and setting \(c_k=c\text{.}\)
🔗

🔗
The integer

\begin{align*} x \amp =m_1c_1M_1+m_2c_2M_2+\cdots +m_nc_nM_m \end{align*}

is a solution to the system of congruences (2.9.8).

🔗

🔗

🔗

Example 2.9.7. CRT for integers.

Find the unique number \(x\in \{0,1\dots, 769\}\) satisfying

\begin{align} x \amp \equiv 4 \pmod{7}\tag{2.9.12}\\ x \amp \equiv 8 \pmod{10}\tag{2.9.13}\\ x \amp \equiv 3 \pmod{11} \tag{2.9.14} \end{align}

🔗

Solution.

Following the algorithm described in the remark above, we first compute the constants

\begin{align*} M_1 \amp = 110 \amp M_2\amp 77 \amp M_3\amp =70 \end{align*}

Next, to find inverses \(c_k\) of \(M_k\) modulo \(a_k\text{,}\) we may work with \(M_k\boldmod a_k\text{.}\) Thus we have

\begin{align*} M_1\equiv 5 \pmod 7 \amp \implies c_1=3 \amp (3\cdot 5=15\equiv 1\pmod 7)\\ M_2\equiv 7 \pmod{10} \amp \implies c_2=3 \amp (3\cdot 7=21\equiv 1\pmod{10})\\ M_3\equiv 4 \pmod{11} \amp \implies c_3=3 \amp (3\cdot 4=12\equiv 1\pmod{11})\text{.} \end{align*}

We conclude that the integer

\begin{align*} y \amp =4 c_1M_1+8c_2M_2+3c_3M_3\\ \amp = 4(3\cdot 110)+8(3\cdot 77)+3(3\cdot 70) \end{align*}

is a solution to the congruences. To get a solution \(x\) in the desired range, we simply compute \(y\boldmod 770\text{:}\)

\begin{align} y \amp = (7+5)(110)+(20+4)77+(11-2)70\tag{2.9.15}\\ \amp = 770+550+2\cdot 770+4\cdot 77+770-140\tag{2.9.16}\\ \amp \equiv 550+308-140 \pmod{770}\tag{2.9.17}\\ \amp = 718 \pmod{770}\text{.}\tag{2.9.18} \end{align}

It follows that \(x=718\) is the unique element of \(\{0,1,\dots, 769\}\) satisfying the given congruences. (Check that it does!)

🔗

Definition 2.9.8. Euler’s totient function.

Euler’s totient function is the function \(\varphi\colon \Z_{\geq 0}\rightarrow \Z\) defined as

\begin{align*} \varphi(n) \amp =\abs{\{k\in \{0,1,\dots, n-1\}\mid \gcd(k,n)=1\}}\text{.} \end{align*}

In other words, \(\varphi(n)\) is the number of integers in \(\{0,1\dots, n-1\}\) that are relatively prime to \(n\text{.}\)

🔗

Corollary 2.9.9. Euler’s totient function.

Let \(\varphi\) be the Euler totient function. If \(a_1,a_2,\dots, a_n\) are pairwise relatively prime integers, then

\begin{align} \phi(a_1a_2\cdots a_n) \amp = \phi(a_1)\phi(a_2)\cdots \phi(a_n) \text{.}\tag{2.9.19} \end{align}

Additionally, given \(m=\prod_{k=1}^r p_k^{n_k}\text{,}\) where the \(p_k\) are distinct prime integers, we have

\begin{align} \varphi(m) \amp = \prod_{k=1}^{r}p^{n_k-1}(p_k-1) \text{.}\tag{2.9.20} \end{align}

🔗

Proof.

Statement (1) follows immediately from Theorem 2.9.5 and the fact (proven elsewhere) that

\begin{align*} \var\phi(m) \amp = \abs{(\Z/m\Z)^*}\text{.} \end{align*}

For (2), observe first the if \(p\) and \(q\) are distinct prime integers, then \(\gcd(p^j, q^k)=1\) for any positive integers \(j\) and \(k\text{.}\) Thus given the factorization \(m=\prod_{k=1}^r p_k^{n_k}\text{,}\) we have

\begin{align*} \var\phi(m) \amp =\prod_{k=1}^n\var(p_k^{n_k}) \end{align*}

by (1). Furthermore, for any prime power \(p^\ell\) an integer \(k\in \{0,1,\dots, p^\ell-1\}\) is relatively prime to \(p^\ell\) if and only if it is not divisible by \(p\text{,}\) if and only if it is not a multiple of \(p\text{.}\) The set of multiples of \(p\) in \(\{0,1,\dots, p^\ell-1\}\) is

\begin{align*} \{0,p, 2p, 3p, \dots, (p^{\ell-1}-1)p\} \amp =\{kp\mid k\in \{0,2,\dots, p^{\ell}-1\}\}\text{,} \end{align*}

which has cardinality \(p^{\ell-1}\text{.}\) Thus

\begin{align*} \varphi(p^\ell) \amp = p^\ell-p^{\ell-1}=p^{\ell-1}(p-1)\text{.} \end{align*}

🔗

Similarly, in a polynomial ring \(F[x]\) over a field \(F\text{,}\) ideals \((f)\) and \((g)\) are coprime if and only if the polynomials \(f\) and \(g\) are relatively prime as polynomials. We haven’t said exactly what that means yet, and indeed will say much more about it when we discuss PIDs and factorization into irreducibles in more detail. For the time being, we include a useful sufficient (though not necessary) condition for two polynomials to have coprime ideals.

🔗

Corollary 2.9.10. Coprime ideals: monic irreducibles.

Let \(F\) be a field. If \(f\) and \(g\) are distinct monic irreducible polynomials in \(F[x]\text{,}\) then the ideals \((f)\) and \((g)\) are coprime.

🔗

Proof.

We use condition (3) of Proposition 2.9.4. Suppose \(h\in F[x]\) divides \(f\) and \(g\text{.}\) Since \(f\) is irreducible, either \(h(x)=c\in F^*\) is a unit, or \(h=cf\) for some unit \(c\in F^*\text{.}\) If the latter is the case, then since \(h=cf\mid g\) it follows that \(f\mid g\text{.}\) But since \(g\) is irreducible and \(f\) is not a unit, we must have \(f=dg\) for some unit \(d\in F^*\text{.}\) Lastly, since \(f\) and \(g\) are monic, it follows that \(d=1\) and \(f=g\text{:}\) a contradiction. We conclude that \(h\) is a unit, showing that the only common divisors of \(f\) and \(g\) are units. Thus \((f)\) and \((g)\) are relatively prime.

🔗

Example 2.9.11. CRT in polynomial rings.

Exhibit an isomorphism between the given ring and a product of fields.

\(\displaystyle \R[x]/(x^3-x)\)
🔗

🔗
\(\displaystyle \R[x]/(x^3-1)\)
🔗

🔗
\(\displaystyle \F_3[x]/(x^2+2)\)
🔗

🔗

🔗

Solution.

We have \(x^3-x=x(x^2-1)=x(x-1)(x-2)\text{.}\) The polynomials \(f(x)=x\text{,}\) \(g(x)=x-1\text{,}\) \(h(x)=x-2\) are distinct, irreducible (since they are of degree 1), and monic. By Corollary 2.9.10, the CRT applies and we have

\begin{align*} \R[x]/(x^3-x) \amp \cong \R[x]/(x)\times \R[x]/(x-1)\times \R[x]/(x+1)\\ \amp \cong \R\times \R\times \R\text{.} \end{align*}

🔗

🔗
We have \(x^3-1=(x-1)(x^2+x+1)\text{.}\) The polynomials \(f(x)=x-1\) and \(g(x)=x^2+x+1\) are distinct, monic, and irreducible (the latter since it has no roots in \(\R\)). By Corollary 2.9.10, the CRT applies and we have

\begin{align*} \R[x]/(x^3-1) \amp \cong \R[x]/(x-1)\times \R[x]/(x^2+x+1)\\ \amp \cong \R\times \C\text{.} \end{align*}

See Example 2.8.15 for the isomorphism \(\R[x]/(x^2+x+1)\cong \C\text{.}\)

🔗

🔗
The polynomial \(x^2+2\) factors as \((x-1)(x-2)=(x+1)(x+2)\) in \(\F_3[x]\text{.}\) The ideals \((x-1)\) and \((x-2)\) are coprime by Corollary 2.9.10, and thus we have

\begin{align*} \F_3[x]/(x^2+2) \amp \cong \F_3[x]/(x-1)\times \F_3[x]/(x-2)\\ \amp \cong \F_3\times \F_3\text{.} \end{align*}

🔗

🔗

🔗

Prev Top Next