# Chinese remainder theorem

The Chinese Remainder Theorem is a result about congruences in number theory and its generalizations in abstract algebra. It was first published in the 3rd to 5th centuries by Chinese mathematician Sun Tzu.

In its basic form, the Chinese remainder theorem will determine a number n that when divided by some given divisors leaves given remainders.

For example, what is the lowest number n that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2? A common introductory example is a woman who tells a policeman that she lost her basket of eggs, and that if she took three at a time out of it, she was left with 2, if she took five at a time out of it she was left with 3, and if she took seven at a time out of it she was left with 2. She then asks the policeman what is the minimum number of eggs she must have had. The answer to both problems is 23.

## Theorem statement

The original form of the theorem, contained in a third-century AD book The Mathematical Classic of Sun Zi (孫子算經) by Chinese mathematician Sun Tzu and later generalized with a complete solution called Da yan shu(大衍術) in a 1247 book by Qin Jiushao, the Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections) is a statement about simultaneous congruences (see modular arithmetic).

Suppose n1, n2, …, nk are positive integers which are pairwise coprime. Then, for any given sequence of integers a1,a2, …, ak, there exists an integer x solving the following system of simultaneous congruences.

\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &{}\ \ \vdots \\ x &\equiv a_k \pmod{n_k} \end{align}

Furthermore, all solutions x of this system are congruent modulo the product, N = n1n2nk.

Hence $\scriptstyle x \;\equiv\; y \pmod{n_i}$ for all $\scriptstyle 1 \;\leq\; i \;\leq\; k$, if and only if $\scriptstyle x \;\equiv\; y \pmod{N}$.

Sometimes, the simultaneous congruences can be solved even if the ni's are not pairwise coprime. A solution x exists if and only if:

$a_i \equiv a_j \pmod{\gcd(n_i,n_j)} \qquad \text{for all }i\text{ and }j.$

All solutions x are then congruent modulo the least common multiple of the ni.

Sun Tzu's work contains neither a proof nor a full algorithm. What amounts to an algorithm for solving this problem was described by Aryabhata (6th century; see Kak 1986). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).

A modern restatement of the theorem in algebraic language is that for a positive integer $\scriptstyle n$ with prime factorization $\scriptstyle p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}$ we have the isomorphism between a ring and the direct product of its prime power parts:

$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p_1^{r_1}\mathbb{Z} \times \mathbb{Z}/p_2^{r_2}\mathbb{Z} \times \cdots \times \mathbb{Z}/p_k^{r_k}\mathbb{Z}.$

## Existence

Existence can be seen by an explicit construction of $\scriptstyle x$. We will use the notation $\scriptstyle [a^{-1}]_b$ to denote the multiplicative inverse of $\scriptstyle a \pmod{b}$ as calculated by the Extended Euclidean algorithm, it is defined exactly when $\scriptstyle a$ and $\scriptstyle b$ are coprime; the following construction explains why the coprimality condition is needed.

### Case of two equations

Given the system (corresponding to $\scriptstyle k \,=\, 2$)

\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2}. \end{align}

Since $\scriptstyle \gcd(n_1, n_2) \,=\, 1$, we have from Bézout's identity

$n_2 [n_2^{-1}]_{n_1} + n_1 [n_1^{-1}]_{n_2} = 1.$

This is true because we agreed to use the inverses which came out of the Extended Euclidian algorithm, for any other inverses, it would not neccessarily hold true, but only hold true $\pmod{n_1n_2}$.

Multiplying both sides by $\scriptstyle x$, we get

$x = x n_2 [n_2^{-1}]_{n_1} + x n_1 [n_1^{-1}]_{n_2}.$

If we take the congruence modulo $\scriptstyle n_1$ for the right-hand-side expression, it is readily seen that

$x \underbrace{n_2 [n_2^{-1}]_{n_1}}_1 + x \underbrace{n_1}_0 [n_1^{-1}]_{n_2} \equiv x \times 1 + x \times 0 \times [n_1^{-1}]_{n_2} \equiv x \pmod {n_1}.$

But we know that

$x \equiv a_1 \pmod {n_1},$

thus this suggests that the coefficient of the first term on the right-hand-side expression can be replaced by $\scriptstyle a_1$. Similarly, we can show that the coefficient of the second term can be substituted by $\scriptstyle a_2$.

We can now define the value

$x := a_1 n_2 [n_2^{-1}]_{n_1} + a_2 n_1 [n_1^{-1}]_{n_2}$

and it is seen to satisfy both congruences by reducing. For example

$a_1 n_2 [n_2^{-1}]_{n_1} + a_2 n_1 [n_1^{-1}]_{n_2} \equiv a_1 \times 1 + a_2 \times 0 \times [n_1^{-1}]_{n_2} \equiv a_1 \pmod {n_1}.$

### General case

The same type of construction works in the general case of $\scriptstyle k$ congruence equations. Let $\scriptstyle N \;=\; n_1 n_2 \cdots n_k$ be the product of every modulus then define

$x := \sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}$

and this is seen to satisfy the system of congruences by a similar calculation as before.

## Finding the solution with basic algebra and modular arithmetic

For example, consider the problem of finding an integer x such that

\begin{align} x &\equiv 2 \pmod{3}\\ x &\equiv 3 \pmod{4}\\ x &\equiv 1 \pmod{5}. \end{align}

A brute-force approach converts these congruences into sets and writes the elements out to the product of 3×4×5 = 60 (the solutions modulo 60 for each congruence):

x ∈ {2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, …}
x ∈ {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, …}
x ∈ {1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, …}.

To find an x that satisfies all three congruences, intersect the three sets to get:

x ∈ {11, …}.

Which can be expressed as

$x \equiv 11 \pmod{60}.$

Another way to find a solution is with basic algebra, modular arithmetic, and stepwise substitution.

We start by translating these equivalences into equations for some t, s, and u:

• Equation 1: x = 2 + 3 × t (mod 3)
• Equation 2: x = 3 + 4 × s (mod 4)
• Equation 3: x = 1 + 5 × u (mod 5).

Start by substituting the x from equation 1 into equivalence 2: 2 + 3 × t = 3 (mod 4), hence 3 × t = 1 (mod 4), or t = (1/3) (mod 4) = 3 (mod 4), meaning that t = 3 + 4 × s for integer s.

Plug t into equation 1: x = 2 + 3 × t (mod 3) = 2 + 3 × (3 + 4 × s) (mod 3) = 11 + 12 × s (mod 3).

Plug this x into equivalence 3: 11 + 12 × s = 1 (mod 5). Casting out 5s, we get 1 + 2 × s = 1 (mod 5), or 2 × s = 0 (mod 5), meaning that s = 0 + 5 × u for integer u.

Finally, x = 11 + 12 × s = 11 + 12 × (5 × u) = 11 + (60 × u). Since 60 = lcm(3, 4, 5), we have solutions 11, 71, 131, 191, …

## A constructive algorithm to find the solution

The following algorithm only applies if the $\scriptstyle n_i$'s are pairwise coprime. (For simultaneous congruences when the moduli are not pairwise coprime, the method of successive substitution can often yield solutions.)

Suppose, as above, that a solution is required for the system of congruences:

$x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \ldots, k.$

Again, to begin, the product $\scriptstyle N \;=\; n_1n_2 \ldots n_k$ is defined. Then a solution x can be found as follows.

For each i the integers $\scriptstyle n_i$ and $\scriptstyle N/n_i$ are coprime. Using the extended Euclidean algorithm we can find integers $\scriptstyle r_i$ and $\scriptstyle s_i$ such that $\scriptstyle r_in_i \,+\, s_iN/n_i \;=\; 1$. Then, choosing the label $\scriptstyle e_i \;=\; s_iN/n_i$, the above expression becomes:

$r_i n_i + e_i = 1. \,\!$

Consider $\scriptstyle e_i$. The above equation guarantees that its remainder, when divided by $\scriptstyle n_i$, must be 1. On the other hand, since it is formed as $\scriptstyle s_iN/n_i$, the presence of N guarantees a remainder of zero when divided by any $\scriptstyle n_j$ when $\scriptstyle j \;\ne\; i$.

$e_i \equiv 1 \pmod{n_i} \quad \mathrm{and} \quad e_i \equiv 0 \pmod{n_j} \quad \mathrm{for} ~ j \ne i$

Because of this, and the multiplication rules allowed in congruences, one solution to the system of simultaneous congruences is:

$x = \sum_{i=1}^k a_i e_i.$

For example, consider the problem of finding an integer x such that

\begin{align} x &\equiv 2 \pmod{3}\\ x &\equiv 3 \pmod{4}\\ x &\equiv 1 \pmod{5}. \end{align}

Using the extended Euclidean algorithm, for x modulo 3 and 20 [4×5], we find (−13) × 3 + 2 × 20 = 1, i.e. e1 = 40. For x modulo 4 and 15 [3×5], we get (−11) × 4 + 3 × 15 = 1, i.e. e2 = 45. Finally, for x modulo 5 and 12 [3×4], we get 5 × 5 + (−2) × 12 = 1, i.e. e3 = −24. A solution x is therefore 2 × 40 + 3 × 45 + 1 × (−24) = 191. All other solutions are congruent to 191 modulo 60, [3 × 4 × 5 = 60], which means they are all congruent to 11 modulo 60.

Note: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of $\scriptstyle e_1 \;=\; -20$, $\scriptstyle e_2 \;=\; -15$, and $\scriptstyle e_3 \;=\; -24$. These sets however will produce the same solution; i.e., (−20)2 + (−15)3 + (−24)1 = −109 = 11 modulo 60.

## Statement for principal ideal domains

For a principal ideal domain R the Chinese remainder theorem takes the following form: If u1, …, uk are elements of R which are pairwise coprime, and u denotes the product u1uk, then the quotient ring R/uR and the product ring R/u1R× … × R/ukR are isomorphic via the isomorphism

$f: R/uR \rightarrow R/u_1R \times \cdots \times R/u_k R$

such that

$f(x +uR) = (x + u_1R, \ldots, x + u_kR) \quad\mbox{ for every } x \in R.$

This map is well-defined and an isomorphism of rings; the inverse isomorphism can be constructed as follows. For each i, the elements ui and u/ui are coprime, and therefore there exist elements r and s in R with

$r u_i + s u/u_i = 1. \,\!$

Set ei = s u/ui. Then the inverse of f is the map

$g: R/u_1R \times \cdots \times R/u_kR \rightarrow R/uR$

such that

$g(a_1 + u_1R, \ldots, a_k + u_kR) = \left( \sum_{i=1}^k a_i \frac{u}{u_i} \left[\left(\frac{u}{u_i}\right)^{-1}\right]_{u_i} \right) + uR \quad\mbox{ for all }a_1, \ldots, a_k \in R.$

This statement is a straightforward generalization of the above theorem about integer congruences: the ring Z of integers is a principal ideal domain, the surjectivity of the map f shows that every system of congruences of the form

$x \equiv a_i \pmod{u_i} \quad\mathrm{for}\; i = 1, \ldots, k$

can be solved for x, and the injectivity of the map f shows that all the solutions x are congruent modulo u.

## Statement for general rings

The general form of the Chinese remainder theorem, which implies all the statements given above, can be formulated for commutative rings and ideals. If R is a commutative ring and I1, …, Ik are ideals of R which are pairwise coprime (meaning that $\scriptstyle I_i \,+\, I_j \;=\; R$ for all $i \neq j$), then the product I of these ideals is equal to their intersection, and the quotient ring R/I is isomorphic to the product ring R/I1 × R/I2 × … × R/Ik via the isomorphism

$f: R/I \rightarrow R/I_1 \times \cdots \times R/I_k$

such that

$f(x + I) = (x + I_1, \ldots, x + I_k) \quad\text{ for all } x \in R.$

Here is a version of the theorem where R is not required to be commutative:

Let R be any ring with 1 (not necessarily commutative) and $\scriptstyle I_1,\, \ldots,\, I_n$ be pairwise coprime 2-sided ideals. Then the canonical R-module homomorphism $\scriptstyle R \;\rightarrow\; R/I_1 \,\times\, \cdots \,\times\, R/I_k$ is onto, with kernel $\scriptstyle I_1 \,\cap\, \cdots \,\cap\, I_k$. Hence, $\scriptstyle R/(I_1 \,\cap\, \cdots \,\cap\, I_k) \,\simeq\, R/I_1 \,\times\, \cdots \,\times\, R/I_k$ (as R-modules).

## Applications

• In the RSA algorithm calculations are made modulo n, where n is a product of two large prime numbers p and q. 1,024-, 2,048- or 4,096-bit integers n are commonly used, making calculations in $\scriptstyle \Bbb{Z}/n\Bbb{Z}$ very time-consuming. By the Chinese remainder theorem, however, these calculations can be done in the isomorphic ring $\scriptstyle \Bbb{Z}/p\Bbb{Z} \,\oplus\, \Bbb{Z}/q\Bbb{Z}$ instead. Since p and q are normally of about the same size, that is about $\scriptstyle \sqrt{n}$, calculations in the latter representation are much faster. Note that RSA algorithm implementations using this isomorphism are more susceptible to fault injection attacks.
• The following example shows a connection with the classic polynomial interpolation theory. Let r complex points ("interpolation nodes") $\scriptstyle \lambda_1,\, \ldots,\, \lambda_r$ be given, together with the complex data $\scriptstyle a_{j,k}$, for all $\scriptstyle 1 \,\leq\, j \,\leq\, r$ and $\scriptstyle 0 \,\leq\, k \,<\, \nu_j$. The general Hermite interpolation problem asks for a polynomial $\scriptstyle P(x) \,\in\, \C[x]$ taking the prescribed derivatives in each node $\scriptstyle \lambda_j$:
$P^{(k)}(\lambda_j) = a_{j, k}\quad\forall 1 \leq j \leq r, 0 \leq k < \nu_j.$
Introducing the polynomials
$A_j(x) := \sum_{k=0}^{\nu_j - 1}\frac{a_{j, k}}{k!}(x - \lambda_j)^k$
the problem may be equivalently reformulated as a system of $\scriptstyle r$ simultaneous congruences:
$P(x) \equiv A_j(x) \pmod {(x - \lambda_j)^{\nu_j}}, \quad\forall 1 \leq j \leq r.$
By the Chinese remainder theorem in the principal ideal domain $\scriptstyle \C[x]$, there is a unique such polynomial $\scriptstyle P(x)$ with degree $\scriptstyle \deg(P) \;<\; n \;:=\; \sum_j\nu_j$. A direct construction, in analogy with the above proof for the integer number case, can be performed as follows. Define the polynomials $\scriptstyle Q \;:=\; \prod_{i=1}^{r}(x \,-\, \lambda_i)^{\nu_i}$ and $\scriptstyle Q_j \;:=\; \frac{Q}{(x \,-\, \lambda_j)^{\nu_j}}$. The partial fraction decomposition of $\scriptstyle \frac{1}{Q}$ gives r polynomials $\scriptstyle S_j$ with degrees $\scriptstyle \deg(S_j) \;<\; \nu_j$ such that
$\frac{1}{Q} = \sum_{i=1}^{r}\frac{S_i}{(x - \lambda_i)^{\nu_i}}$
so that $\scriptstyle 1 = \sum_{i=1}^{r}S_i Q_i$. Then a solution of the simultaneous congruence system is given by the polynomial
$\sum_{i=1}^{r} A_i S_i Q_i = A_j + \sum_{i=1}^{r}(A_i - A_j) S_i Q_i \equiv A_j\pmod{(x - \lambda_j)^{\nu_j}}\quad\forall 1 \leq j \leq r$
and the minimal degree solution is this one reduced modulo $\scriptstyle Q$, that is the unique with degree less than n.
• The Chinese remainder theorem can also be used in secret sharing, which consists of distributing a set of shares among a group of people who, all together (but no one alone), can recover a certain secret from the given set of shares. Each of the shares is represented in a congruence, and the solution of the system of congruences using the Chinese remainder theorem is the secret to be recovered. Secret Sharing using the Chinese Remainder Theorem uses, along with the Chinese remainder theorem, special sequences of integers that guarantee the impossibility of recovering the secret from a set of shares with less than a certain cardinality.
• Dedekind's theorem on the linear independence of characters states (in one of its most general forms) that if M is a monoid and k is an integral domain, then any finite family $\scriptstyle \left(f_i\right)_{i \in I}$ of distinct monoid homomorphisms $\scriptstyle f_i:\, M \,\to\, k$ (where the monoid structure on k is given by multiplication) is linearly independent; i.e., every family $\scriptstyle \left(\alpha_i\right)_{i\in I}$ of elements $\scriptstyle \alpha_i \,\in\, k$ satisfying $\scriptstyle \sum_{i \in I}\alpha_i f_i \;=\; 0$ must be equal to the family $\scriptstyle \left(0\right)_{i \in I}$.
Proof using the Chinese Remainder Theorem: First, assume that k is a field (otherwise, replace the integral domain k by its quotient field, and nothing will change). We can linearly extend the monoid homomorphisms $\scriptstyle f_i:\, M \,\to\, k$ to k-algebra homomorphisms $\scriptstyle F_i:\, k\left[M\right] \,\to\, k$, where $\scriptstyle k\left[M\right]$ is the monoid ring of M over k. Then, the condition $\scriptstyle \sum_{i\in I}\alpha_i f_i \;=\; 0$ yields $\scriptstyle \sum_{i \in I}\alpha_i F_i \;=\; 0$ by linearity. Now, we notice that if $\scriptstyle i \;\neq\; j$ are two elements of the index set I, then the two k-linear maps $\scriptstyle F_i:\, k\left[M\right] \,\to\, k$ and $\scriptstyle F_j:\, k\left[M\right] \,\to\, k$ are not proportional to each other (because if they were, then $\scriptstyle f_i$ and $\scriptstyle f_j$ would also be proportional to each other, and thus equal to each other since $\scriptstyle f_i\left(1\right) \;=\; 1 \;=\; f_j\left(1\right)$ (since $\scriptstyle f_i$ and $\scriptstyle f_j$ are monoid homomorphisms), contradicting the assumption that they be distinct). Hence, their kernels $\scriptstyle \mathrm{Ker} F_i$ and $\scriptstyle \mathrm{Ker} F_j$ are distinct. Now, $\scriptstyle \mathrm{Ker} F_i$ is a maximal ideal of $\scriptstyle k\left[M\right]$ for every $\scriptstyle i \,\in\, I$ (since $\scriptstyle k\left[M\right] / \mathrm{Ker} F_i \;\cong\; F_i\left(k\left[M\right]\right) \;=\; k$ is a field), and the ideals $\scriptstyle \mathrm{Ker} F_i$ and $\scriptstyle \mathrm{Ker} F_j$ are coprime whenever $\scriptstyle i \;\neq\; j$ (since they are distinct and maximal). The Chinese Remainder Theorem (for general rings) thus yields that the map
$\phi: k\left[M\right] / K \to \prod_{i \in I}k\left[M\right] / \mathrm{Ker} F_i$
given by
$\phi\left(x + K\right) = \left(x + \mathrm{Ker} F_i\right)_{i \in I}$ for all $x\in k\left[M\right]$
is an isomorphism, where $\scriptstyle K \;=\; \prod_{i \in I}\mathrm{Ker} F_i \;=\; \bigcap_{i \in I}\mathrm{Ker} F_i$. Consequently, the map
$\Phi: k\left[M\right] \to \prod_{i \in I}k\left[M\right] / \mathrm{Ker} F_i$
given by
$\Phi\left(x\right) = \left(x + \mathrm{Ker} F_i\right)_{i \in I}$ for all $x \in k\left[M\right]$
is surjective. Under the isomorphisms $\scriptstyle k\left[M\right] / \mathrm{Ker} F_i \,\to\, F_i\left(k\left[M\right]\right) \;=\; k$, this map $\scriptstyle \Phi$ corresponds to the map
$\psi: k\left[M\right] \to \prod_{i \in I}k$
given by
$x \mapsto \left[F_i\left(x\right)\right]_{i \in I}$ for every $x \in k\left[M\right].$
Now, $\scriptstyle \sum_{i \in I}\alpha_i F_i \;=\; 0$ yields $\scriptstyle \sum_{i \in I}\alpha_i u_i \;=\; 0$ for every vector $\scriptstyle \left(u_i\right)_{i \in I}$ in the image of the map $\scriptstyle \psi$. Since $\scriptstyle \psi$ is surjective, this means that $\scriptstyle \sum_{i \in I}\alpha_i u_i \;=\; 0$ for every vector $\scriptstyle \left(u_i\right)_{i \in I} \,\in\, \prod_{i \in I}k$. Consequently, $\scriptstyle \left(\alpha_i\right)_{i \in I} \;=\; \left(0\right)_{i \in I}$, QED.

## Non-commutative case: a caveat

Sometimes in the commutative case, the conclusion of the Chinese Remainder Theorem is stated as $\scriptstyle R/(I_1 I_2\cdots I_k) \,\simeq\, R/I_1 \,\times\, \cdots \,\times\, R/I_k$. This version does not hold in the non-commutative case, since $\scriptstyle(I_1 \,\cap\, \cdots \,\cap\, I_k) \neq (I_1 I_2\cdots I_k)$, as can be seen from the following example

Consider the ring R of non-commutative real polynomials in x and y. Let I be the principal two-sided ideal generated by x and J the principal two-sided ideal generated by $\scriptstyle xy \,+\, 1$. Then $\scriptstyle I \,+\, J \;=\; R$ but $\scriptstyle I \,\cap\, J \;\neq\; IJ$.

### Proof

Observe that I is formed by all polynomials with an x in every term and that every polynomial in J vanishes under the substitution $\scriptstyle y \;=\; -1/x$. Consider the polynomial $\scriptstyle p \;=\; (xy \,+\, 1)x$. Clearly $\scriptstyle p \,\in\, I \,\cap\, J$. Define a term in R as an element of the multiplicative monoid of R generated by x and y. Define the degree of a term as the usual degree of the term after the substitution $\scriptstyle y \;=\; x$. On the other hand, suppose $q \,\in\, J$. Observe that a term in q of maximum degree depends on y otherwise q under the substitution $\scriptstyle y \;=\; -1/x$ can not vanish. The same happens then for an element $\scriptstyle q \,\in\, IJ$. Observe that the last y, from left to right, in a term of maximum degree in an element of $\scriptstyle IJ$ is preceded by more than one x. (We are counting here all the preceding xs. E.g., in $\scriptstyle x^2yxyx^5$ the last y is preceded by $\scriptstyle 3$ xs.) This proves that $\scriptstyle (xy \,+\, 1)x \,\notin\, IJ$ since that last y in a term of maximum degree ($\scriptstyle xyx$) is preceded by only one x. Hence $\scriptstyle I \,\cap\, J \;\neq\; IJ$.

On the other hand, it is true in general that $\scriptstyle I \,+\, J = R$ implies $\scriptstyle I \,\cap\, J \;=\; IJ \,+\, JI$. To see this, note that $\scriptstyle I \,\cap\, J \;=\; (I \,\cap\, J) (I \,+\, J) \;\subset\; IJ \,+\, JI$, while the opposite inclusion is obvious. Also, we have in general that, provided $\scriptstyle I_1,\, \ldots,\, I_m$ are pairwise coprime two-sided ideals in R, the natural map

$R / (I_1 \cap I_2 \cap \ldots \cap I_m) \rightarrow R/I_1 \oplus R/I_2 \oplus \cdots \oplus R/I_m$

is an isomorphism. Note that $\scriptstyle I_1 \,\cap\, I_2 \,\cap\, \ldots \,\cap\, I_m$ can be replaced by a sum over all orderings of $\scriptstyle I_1,\, \ldots,\, I_m$ of their product (or just a sum over enough orderings, using inductively that $\scriptstyle I \,\cap\, J \;=\; IJ \,+\, JI$ for coprime ideals $\scriptstyle I,\, J$).