The Chinese Remainder Theorem

Simultaneous congruences to relatively prime moduli have a solution, unique modulo the product, found from Bezout's identity; with a common factor, a solution exists exactly when the remainders agree modulo the gcd. In the language of rings, Z_mn is isomorphic to Z_m x Z_n exactly when gcd(m, n) = 1, proved in full with Z_45 and Z_5 x Z_9 as the running example. Idempotents, computing powers and products through the isomorphism, square roots of 1, RSA decryption in the form of RFC 8017, Euler's phi as a product, any number of moduli with Sunzi's puzzle, and the same theorem for polynomials.

A problem in the Sunzi suanjing (Master Sun's Mathematical Manual) asks for a number of objects which, counted in threes, leave 2 over; counted in fives, leave 3; and counted in sevens, leave 2. The answer given is 23. The book also gives a recipe that works for any three remainders: multiply the remainder for threes by 70, the remainder for fives by 21, the remainder for sevens by 15, add, and subtract multiples of 105 (O'Connor and Robertson, MacTutor). Here $2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233$, and $233 - 210 = 23$. The recipe works because 70 leaves remainders 1, 0, 0 on division by 3, 5 and 7, while 21 leaves 0, 1, 0 and 15 leaves 0, 0, 1. Each multiplier controls one remainder and is invisible to the other two. Can such multipliers always be found, and what does their existence say about arithmetic modulo $3 \cdot 5 \cdot 7$?

The Chinese remainder theorem answers both questions. When the moduli are pairwise relatively prime, every choice of remainders comes from exactly one number modulo their product. In the language of rings, $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$ when $\gcd(m, n) = 1$. The running example is $45 = 5 \cdot 9$. Arithmetic modulo 45 turns out to be arithmetic modulo 5 and modulo 9 carried out side by side, and that changes how several earlier computations look: why $x^2 = 1$ has eight solutions in $\mathbb{Z}_{24}$, why Euler's $\varphi$ multiplies, and how the owner of an RSA key decrypts faster.

First we solve two congruences at once with Bezout's identity, and see what changes when the moduli share a factor. Then we restate the result as a ring isomorphism and prove that it fails without relatively prime moduli. Next we use the isomorphism: its idempotents, powers and products computed in pieces, square roots of 1, RSA decryption and Euler's $\varphi$. Finally we extend it to any number of moduli and to polynomials.

This is the second article of Homomorphisms and the Chinese Remainder Theorem, and it assumes the first, Ring Homomorphisms and Isomorphisms. It also uses direct products, the units of $\mathbb{Z}_n$, and Bezout's identity from Divisibility and the Euclidean Algorithm. The course proved the theorem in the setting of §3.3 of the course text (Hungerford, 2014), which treats systems of congruences in an optional chapter (§14.1); Judson (2026, §16.5) proves the congruence form.

Two congruences at once

The article on the integers modulo $n$ left open the question of finding a number that is 2 modulo 5 and 4 modulo 9. Following Sunzi, look for two multipliers: one that is 1 modulo 5 and 0 modulo 9, and one that is 0 modulo 5 and 1 modulo 9. Bezout's identity for 5 and 9 supplies both at once:

$$5 \cdot 2 + 9 \cdot (-1) = 1.$$

The term $5 \cdot 2 = 10$ is a multiple of 5, and it is $1 - 9 \cdot (-1) \equiv 1 \pmod 9$. The term $9 \cdot (-1) = -9$ is a multiple of 9, and it is $1 - 10 \equiv 1 \pmod 5$. Modulo 45, $-9$ is 36. So with $e_1 = 36$ and $e_2 = 10$,

$$x = 2 e_1 + 4 e_2 = 72 + 40 = 112 \equiv 22 \pmod{45},$$

and indeed $22 = 4 \cdot 5 + 2 = 2 \cdot 9 + 4$. The same multipliers solve every such pair: $x \equiv 3 \pmod 5$ and $x \equiv 7 \pmod 9$ give $3 \cdot 36 + 7 \cdot 10 = 178 \equiv 43$.

The general statement follows the same plan. Bezout's identity $ms + nt = 1$ splits 1 into a multiple of $m$ and a multiple of $n$. Each piece is 1 for one modulus and 0 for the other, so it can carry one remainder without disturbing the other.

Theorem. Let $m$ and $n$ be relatively prime positive integers, and let $a$ and $b$ be integers. Then the system

$$x \equiv a \pmod m, \qquad x \equiv b \pmod n$$

has a solution, and any two solutions are congruent modulo $mn$. If $ms + nt = 1$, one solution is $x = a\,nt + b\,ms$.

Proof. Existence. Since $\gcd(m, n) = 1$, Bezout's identity gives integers $s$ and $t$ with $ms + nt = 1$. Then $nt = 1 - ms \equiv 1 \pmod m$ and $nt \equiv 0 \pmod n$; likewise $ms \equiv 0 \pmod m$ and $ms = 1 - nt \equiv 1 \pmod n$. So

$$a\,nt + b\,ms \equiv a \cdot 1 + b \cdot 0 = a \pmod m, \qquad a\,nt + b\,ms \equiv a \cdot 0 + b \cdot 1 = b \pmod n.$$

Uniqueness. If $x$ and $y$ are solutions, then $x \equiv y$ modulo $m$ and modulo $n$. So $m$ and $n$ both divide $x - y$, and by the lemma on relatively prime moduli so does $mn$. Conversely, anything congruent to a solution modulo $mn$ is a solution. $\blacksquare$

So the solutions form exactly one class modulo $mn$. Judson (2026, Lemma 16.5.1) proves the same statement by a different route: start from $a + km$, which satisfies the first congruence for every $k$, and choose $k$ to satisfy the second. The proof here produces the two multipliers $e_1 = nt$ and $e_2 = ms$ once. After that, every system with the same moduli costs two multiplications.

When the moduli share a factor

What if the moduli are not relatively prime? Then not every pair of remainders can occur, because the two congruences already say something about $x$ modulo $d = \gcd(m, n)$, and they must agree there.

Proposition. Let $m$ and $n$ be positive integers with $d = \gcd(m, n)$ and $L = \operatorname{lcm}(m, n)$. The system $x \equiv a \pmod m$, $x \equiv b \pmod n$ has a solution if and only if $a \equiv b \pmod d$, and then its solutions form one class modulo $L$.

Proof. If $x$ is a solution, then $x = a + mk = b + nl$ for some integers $k$ and $l$, so $a - b = nl - mk$ is divisible by $d$. Conversely, suppose $a - b = dq$, and write $d = ms + nt$ by Bezout's identity. Put $x = a - msq$. Then $x \equiv a \pmod m$, and

$$x - b = (a - b) - msq = dq - msq = q(d - ms) = q\,nt,$$

so $x \equiv b \pmod n$. Two solutions differ by a common multiple of $m$ and $n$, which is a multiple of $L$ (the least common multiple divides every common multiple); and adding a multiple of $L$ to a solution gives a solution. $\blacksquare$

For example, $x \equiv 3 \pmod 6$ and $x \equiv 7 \pmod{10}$ have $d = 2$, and $3 \equiv 7 \pmod 2$, so there is one solution modulo 30; the script finds 27 (and 57 in the range up to 59). But $x \equiv 3 \pmod 6$ and $x \equiv 4 \pmod{10}$ have no solution, since the first makes $x$ odd and the second makes it even. When $d = 1$ the condition is empty and $L = mn$, which is the theorem.

The ring version

A remainder modulo $mn$ determines the remainders modulo $m$ and $n$. The theorem says that, when $\gcd(m, n) = 1$, the converse holds as well. Does the correspondence also respect arithmetic? It does, and that makes it an isomorphism of rings.

A small lemma lets homomorphisms into a product be checked one coordinate at a time.

Lemma. Let $R$, $S$ and $T$ be rings and $f_1: R \to S$ and $f_2: R \to T$ functions. Then $f(r) = (f_1(r), f_2(r))$ is a homomorphism from $R$ to $S \times T$ if and only if $f_1$ and $f_2$ are homomorphisms.

Proof. The operations of $S \times T$ are coordinatewise. So $f(a + b) = f(a) + f(b)$ says $(f_1(a + b), f_2(a + b)) = (f_1(a) + f_1(b), f_2(a) + f_2(b))$, which holds exactly when both coordinates agree. The same goes for products. $\blacksquare$

Here is the plan of the main proof. The lemma makes the remainder map a homomorphism, because each coordinate is a change of modulus. The divisibility lemma makes it one-to-one. Counting makes it onto, and the existence proof above writes down its inverse.

Theorem (Chinese remainder theorem). Let $m, n \ge 2$ be relatively prime. Then

$$\theta: \mathbb{Z}_{mn} \to \mathbb{Z}_m \times \mathbb{Z}_n, \qquad \theta([a]_{mn}) = ([a]_m, [a]_n),$$

is an isomorphism of rings. Its inverse is $([u]_m, [v]_n) \mapsto [u e_1 + v e_2]_{mn}$, where $e_1 = nt$ and $e_2 = ms$ for any integers $s, t$ with $ms + nt = 1$.

Proof. Well defined. Each coordinate is a change of modulus from $mn$ to a divisor of $mn$, which is a well-defined homomorphism (changing the modulus). By the lemma, $\theta$ is a homomorphism.

One-to-one. If $\theta([a]) = \theta([b])$, then $a \equiv b$ modulo $m$ and modulo $n$, hence modulo $mn$ by the lemma on relatively prime moduli, so $[a]_{mn} = [b]_{mn}$.

Onto. Both rings have $mn$ elements, and a one-to-one function between finite sets of the same size is onto. Explicitly, for $([u]_m, [v]_n)$ the element $[ue_1 + ve_2]_{mn}$ maps to it, by the existence part of the previous theorem.

So $\theta$ is a bijective homomorphism, and the inverse is the map just described. $\blacksquare$

For $m = 5$ and $n = 9$, the script checks all 2,025 sums and all 2,025 products. For example, $17 \mapsto (2, 8)$ and $23 \mapsto (3, 5)$, while $17 \cdot 23 = 391 \equiv 31 \pmod{45}$ and $31 \mapsto (1, 4)$. Coordinatewise, $2 \cdot 3 = 6 \equiv 1 \pmod 5$ and $8 \cdot 5 = 40 \equiv 4 \pmod 9$. In the same way, $-1$ in $\mathbb{Z}_{45}$, which is 44, corresponds to $(-1, -1) = (4, 8)$: an isomorphism sends $1$ to $1$ and so $-1$ to $-1$.

Counting 0, 1, 2, ... while tracking two remainders. Left: each a in Z45 is placed in row a mod 5 and column a mod 9. Each step moves one row down and one column right, wrapping around. Notice that the count fills all 45 cells before returning to 0, so each pair of remainders comes from exactly one a. Right: the same with remainders modulo 6 and 9 for a in Z54. The count returns to the corner at 18 = lcm(6, 9) and repeats, reaching only 18 of the 54 cells.
Counting 0, 1, 2, ... while tracking two remainders. Left: each a in Z_45 is placed in row a mod 5 and column a mod 9. Each step moves one row down and one column right, wrapping around. Notice that the count fills all 45 cells before returning to 0, so each pair of remainders comes from exactly one a. Right: the same with remainders modulo 6 and 9 for a in Z_54. The count returns to the corner at 18 = lcm(6, 9) and repeats, reaching only 18 of the 54 cells.

The figure is the proof in a picture. The element $a$ returns to the pair $(0, 0)$ exactly when $a$ is a common multiple of the two moduli. When they are relatively prime the first such $a$ is their product, so the walk visits every cell before repeating. Otherwise it closes up at the least common multiple and misses most of the grid.

The theorem fails without relatively prime moduli

The right-hand grid suggests that the theorem cannot survive a common factor. To prove it, find a property that the two rings do not share. The idea is that the number $L = \operatorname{lcm}(m, n)$ kills every element of the product when added to itself $L$ times, but it does not kill 1 in $\mathbb{Z}_{mn}$.

Proposition. If $d = \gcd(m, n) > 1$, then $\mathbb{Z}_{mn}$ and $\mathbb{Z}_m \times \mathbb{Z}_n$ are not isomorphic.

Proof. Let $L = \operatorname{lcm}(m, n) = mn/d$ (by the identity $\gcd \cdot \operatorname{lcm} = mn$ of Primes and the Fundamental Theorem of Arithmetic), so $L < mn$. Every element $(u, v)$ of the product satisfies $L(u, v) = (Lu, Lv) = (0, 0)$, since $m$ and $n$ divide $L$. In $\mathbb{Z}_{mn}$ the identity satisfies $L \cdot 1 = [L] \neq 0$, since $0 < L < mn$. So the characteristics differ ($mn$ against at most $L$), and isomorphic rings have the same characteristic (what an isomorphism preserves). $\blacksquare$

For $\mathbb{Z}_{54}$ and $\mathbb{Z}_6 \times \mathbb{Z}_9$, $L = 18$. The map $a \mapsto (a \bmod 6, a \bmod 9)$ sends 18 to $(0, 0)$, and its image has 18 elements, the shaded cells of the figure. For $\mathbb{Z}_{90}$ and $\mathbb{Z}_6 \times \mathbb{Z}_{15}$, $L = 30$. The pair $\mathbb{Z}_{24}$ and $\mathbb{Z}_4 \times \mathbb{Z}_6$ was compared in Subrings and Direct Products of Rings, and $\mathbb{Z}_9$ against $\mathbb{Z}_3 \times \mathbb{Z}_3$ in Ring Homomorphisms and Isomorphisms. So the theorem is an "if and only if": $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$ exactly when $\gcd(m, n) = 1$, as Judson (2026, Theorem 9.2.9) proves for the additive groups.

Check your understanding. The map $\mathbb{Z}_{54} \to \mathbb{Z}_6 \times \mathbb{Z}_9$ reaches only 18 of the 54 pairs. Is $(1, 0)$ among them? Is $(3, 0)$? If so, how many $a$ reach it?

Use the proposition on moduli with a common factor, with $d = 3$. The pair $(1, 0)$ needs $1 \equiv 0 \pmod 3$, which fails, so no $a$ reaches it. The pair $(3, 0)$ needs $3 \equiv 0 \pmod 3$, which holds, so it is reached by one class modulo 18. In $\mathbb{Z}_{54}$ that class has $54 / 18 = 3$ members, and the script finds them: 9, 27 and 45.

Idempotents

Back to $\mathbb{Z}_{45}$. The multipliers $e_1 = 36$ and $e_2 = 10$ correspond to $(1, 0)$ and $(0, 1)$ in $\mathbb{Z}_5 \times \mathbb{Z}_9$. In the product, $(1, 0)^2 = (1, 0)$, $(0, 1)^2 = (0, 1)$, $(1, 0)(0, 1) = (0, 0)$ and $(1, 0) + (0, 1) = (1, 1)$. So the isomorphism forces

$$e_1^2 = e_1, \qquad e_2^2 = e_2, \qquad e_1 e_2 = 0, \qquad e_1 + e_2 = 1$$

in $\mathbb{Z}_{45}$, and the script confirms $36^2 = 36$, $10^2 = 10$, $36 \cdot 10 = 0$ and $36 + 10 = 1$. An element equal to its own square is an idempotent. In $\mathbb{Z}$ the only idempotents are 0 and 1, so the presence of 36 and 10 is a sign that $\mathbb{Z}_{45}$ splits as a product.

The multiples of $e_1$ are the multiples of 9, $\{0, 9, 18, 27, 36\}$, the elements corresponding to $\mathbb{Z}_5 \times \{0\}$. They form a copy of $\mathbb{Z}_5$ inside $\mathbb{Z}_{45}$ whose identity is 36, not 1, much as the corner matrix $E$ of Ring Homomorphisms and Isomorphisms is the identity of a copy of $\mathbb{R}$ inside the $2 \times 2$ matrices without being the identity matrix. Sunzi's 70, 21 and 15 are the three idempotents of $\mathbb{Z}_{105}$ of this kind: each is its own square modulo 105, the product of any two is 0, and their sum is $106 \equiv 1$.

Computing through the isomorphism

What is the isomorphism good for in practice? It lets a computation modulo $mn$ be done modulo $m$ and modulo $n$ separately, then recombined with $e_1$ and $e_2$.

A power. To find $7^{100}$ in $\mathbb{Z}_{45}$:

  • modulo 5, $7 \equiv 2$ and $2^4 \equiv 1$ by Fermat's theorem, so $2^{100} = (2^4)^{25} \equiv 1$;
  • modulo 9, $7$ is a unit and $\varphi(9) = 6$, so by Euler's theorem the exponent can be reduced modulo 6: $100 \equiv 4$, and $7^2 = 49 \equiv 4$, $7^4 \equiv 16 \equiv 7$.

So $7^{100}$ corresponds to $(1, 7)$, which is $1 \cdot 36 + 7 \cdot 10 = 106 \equiv 16$. The script's direct computation agrees: $7^{100} \bmod 45 = 16$.

Check your understanding. Without computing $2^{12}$, predict $2^{12} \bmod 45$.

It is 1. Modulo 5, $2^{12} = (2^4)^3 \equiv 1$, and modulo 9, $2^{12} = (2^6)^2 \equiv 1$ by Euler's theorem. The pair $(1, 1)$ corresponds to 1. The same argument works for every unit of $\mathbb{Z}_{45}$, since 12 is the least common multiple of $\varphi(5) = 4$ and $\varphi(9) = 6$. So every unit satisfies $a^{12} = 1$, half of Euler's exponent $\varphi(45) = 24$, and the script finds that no smaller exponent works for all units. This is the reasoning that Fermat's Little Theorem used for $\mathbb{Z}_{21}$, now in the language of the isomorphism.

Large products from small ones. The moduli 99, 100 and 101 are pairwise relatively prime, with product 999,900. To multiply 1234 by 567, reduce each:

$$1234 \mapsto (46, 34, 22), \qquad 567 \mapsto (72, 67, 62).$$

Multiply coordinatewise, $(46 \cdot 72, 34 \cdot 67, 22 \cdot 62) \equiv (45, 78, 51)$, and recombine. The script does this and gets 699,678, equal to $1234 \cdot 567$. The answer is correct because it is less than 999,900, so it is determined by its class. Each coordinate involves only numbers below about $100^2$, and the three coordinates can be computed independently, by different processors if need be. Judson (2026, §16.5) describes this use in the design of software for parallel machines. Systems that do all arithmetic this way are called residue number systems.

Square roots of 1

The integers modulo $n$ found eight solutions of $x^2 = 1$ in $\mathbb{Z}_{24}$, and eight in $\mathbb{Z}_{1729}$, against two in $\mathbb{Z}_{13}$. The isomorphism explains the counts. A solution in a product is a pair whose coordinates are solutions, so the number of solutions in $\mathbb{Z}_m \times \mathbb{Z}_n$ is the product of the numbers in $\mathbb{Z}_m$ and in $\mathbb{Z}_n$, and isomorphic rings have the same number of solutions.

Proposition. If $n = p_1 p_2 \cdots p_k$ is a product of $k$ distinct odd primes, then $x^2 = 1$ has exactly $2^k$ solutions in $\mathbb{Z}_n$.

Proof. In the field $\mathbb{Z}_p$, $x^2 = 1$ means $(x - 1)(x + 1) = 0$, so $x = 1$ or $x = -1$, since a field has no zero divisors; and $1 \neq -1$ because $p$ is odd. So there are exactly two solutions modulo each $p_i$. By the theorem for several moduli below, $\mathbb{Z}_n \cong \mathbb{Z}_{p_1} \times \cdots \times \mathbb{Z}_{p_k}$, and the solutions there are the $2^k$ tuples of signs. $\blacksquare$

For $1729 = 7 \cdot 13 \cdot 19$ this gives $2^3 = 8$, and the script lists them: $1, 246, 664, 818, 911, 1065, 1483, 1728$. The proposition needs prime moduli, but the counting argument does not: $\mathbb{Z}_{24} \cong \mathbb{Z}_8 \times \mathbb{Z}_3$, and $x^2 = 1$ has 4 solutions in $\mathbb{Z}_8$ (1, 3, 5, 7) and 2 in $\mathbb{Z}_3$, which gives 8. In $\mathbb{Z}_{45} \cong \mathbb{Z}_5 \times \mathbb{Z}_9$ there are $2 \cdot 2 = 4$, namely $1, 19, 26, 44$, corresponding to $(\pm 1, \pm 1)$. A polynomial of degree 2 with four roots is possible only because $\mathbb{Z}_{45}$ is not an integral domain; over a field, a polynomial has at most as many roots as its degree (Irreducible Polynomials and Roots).

RSA decryption

The RSA article decrypted its ciphertext one prime at a time, with the primes $p = 43$ and $q = 71$ and the exponents 13 and 27, reduced modulo $p - 1$ and $q - 1$ by Fermat's little theorem, and found the message to be 5 modulo 43 and 38 modulo 71. It left the recombination to this theorem. The standard specification of RSA does that step in a particular form (Moriarty et al., 2016, §§3.2 and 5.1.2). It stores the private key as $p$, $q$, the reduced exponents $d_P = d \bmod (p - 1)$ and $d_Q = d \bmod (q - 1)$, and the coefficient $q_{\text{inv}} = q^{-1} \bmod p$, and decrypts in four steps:

$$m_1 = C^{d_P} \bmod p, \qquad m_2 = C^{d_Q} \bmod q, \qquad h = (m_1 - m_2)\, q_{\text{inv}} \bmod p, \qquad m = m_2 + q h.$$

With the article's key ($n = 3053$, $d = 1357$) and ciphertext $C = 1280$, $d_P = 13$, $d_Q = 27$ and $q_{\text{inv}} = 20$, since $71 \cdot 20 = 1420 = 33 \cdot 43 + 1$. The script finds $m_1 = 5$, $m_2 = 38$, $h = (5 - 38) \cdot 20 \bmod 43 = 28$ and $m = 38 + 71 \cdot 28 = 2026$, the original message.

This form of the recombination is the theorem's existence proof arranged to keep numbers small. The value $m = m_2 + qh$ is congruent to $m_2$ modulo $q$ for every $h$, and modulo $p$ it is $m_2 + q(m_1 - m_2)q^{-1} \equiv m_1$. Since $0 \le m_2 < q$ and $0 \le h < p$, the result lies between 0 and $pq - 1$, so it is the message itself. The idempotent form gives the same answer: Bezout's identity $43 \cdot (-33) + 71 \cdot 20 = 1$ gives $e_p = 1420$ and $e_q = 1634$ in $\mathbb{Z}_{3053}$, and $5 \cdot 1420 + 38 \cdot 1634 \equiv 2026$. The work saved is in the exponentiations: two powers with exponents and moduli of half the size, instead of one full-size power.

Units and Euler's phi function

The isomorphism also counts units. Since it matches units with units, and the units of a product are the pairs of units, counting gives a formula for Euler's $\varphi$.

Corollary. If $\gcd(m, n) = 1$, then $[a]_{mn}$ is a unit of $\mathbb{Z}_{mn}$ if and only if $[a]_m$ and $[a]_n$ are units, and

$$\varphi(mn) = \varphi(m)\,\varphi(n).$$

Proof. An isomorphism matches units with units (what an isomorphism preserves), and the units of $\mathbb{Z}_m \times \mathbb{Z}_n$ are the pairs of units (Subrings and Direct Products of Rings). Counting, $\mathbb{Z}_{mn}$ has $\varphi(mn)$ units and the product has $\varphi(m)\varphi(n)$. $\blacksquare$

For a prime power, the integers from 1 to $p^k$ that share a factor with $p^k$ are the multiples of $p$, of which there are $p^{k-1}$, so $\varphi(p^k) = p^k - p^{k-1}$. Write $n = p_1^{k_1} \cdots p_r^{k_r}$ as a product of powers of distinct primes. These prime powers are pairwise relatively prime, so the corollary gives

$$\varphi(n) = \prod_{i=1}^{r} \big(p_i^{k_i} - p_i^{k_i - 1}\big) = n \prod_{i=1}^{r} \Big(1 - \frac{1}{p_i}\Big).$$

So $\varphi(45) = \varphi(5)\varphi(9) = 4 \cdot 6 = 24$ and $\varphi(360) = \varphi(8)\varphi(9)\varphi(5) = 4 \cdot 6 \cdot 4 = 96$, which the script confirms by counting. The values $\varphi(1001) = 720$ and $\varphi(1729) = 1296$, used in Fermat's Little Theorem and Units and Zero Divisors in the Integers Modulo n, are instances. The condition $\gcd(m, n) = 1$ cannot be dropped: $\varphi(4)\varphi(6) = 4$, but $\varphi(24) = 8$.

Check your understanding. Of the 105 possible counts in Sunzi's puzzle, from 0 to 104, how many leave a nonzero remainder on division by each of 3, 5 and 7?

A count with all three remainders nonzero is one sharing no factor with $3 \cdot 5 \cdot 7$, that is, a unit modulo 105. The corollary, applied to $105 = 3 \cdot 35$ and then to $35 = 5 \cdot 7$, gives $\varphi(105) = \varphi(3)\varphi(5)\varphi(7) = 2 \cdot 4 \cdot 6 = 48$. The script counts 48.

Any number of moduli

Sunzi's puzzle has three moduli, and the theorem extends to any number, provided every pair is relatively prime.

Theorem. Let $n_1, \ldots, n_k \ge 2$ be pairwise relatively prime, that is, $\gcd(n_i, n_j) = 1$ whenever $i \neq j$, and let $N = n_1 n_2 \cdots n_k$. Then

$$\mathbb{Z}_N \cong \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \cdots \times \mathbb{Z}_{n_k}, \qquad [a]_N \mapsto ([a]_{n_1}, \ldots, [a]_{n_k}).$$

Equivalently, for any integers $a_1, \ldots, a_k$ the system $x \equiv a_i \pmod{n_i}$, $i = 1, \ldots, k$, has a solution, and any two solutions are congruent modulo $N$.

The proof is the one for two moduli. The only new step is that the divisibility lemma still applies, because the product of the first $k - 1$ moduli is relatively prime to the last.

Proof. The map is well defined and a homomorphism by the lemma on products, applied coordinate by coordinate. It is one-to-one: if $a \equiv b$ modulo every $n_i$, then $N \mid a - b$, by induction on $k$ using the lemma on relatively prime moduli. The induction works because $n_1 \cdots n_{k-1}$ and $n_k$ are relatively prime: a prime dividing both would divide some $n_i$ with $i < k$, by Euclid's lemma, and also $n_k$. Both sides have $N$ elements, so the map is onto. The system has a solution because the map is onto, and the solutions form one class because it is one-to-one. $\blacksquare$

Judson (2026, Theorem 16.5.3) proves the congruence form by induction on the number of congruences, solving two at a time. As in the case of two moduli, the inverse map can be written with idempotents. Here $e_i$ is the element that is 1 modulo $n_i$ and 0 modulo the others, found from Bezout's identity for $n_i$ and $N/n_i$. For Sunzi's moduli 3, 5 and 7 these are 70, 21 and 15, and the recipe of the opening paragraph is the formula $x = 2e_1 + 3e_2 + 2e_3$.

Applied to the prime factorization, the theorem gives $\mathbb{Z}_n \cong \mathbb{Z}_{p_1^{k_1}} \times \cdots \times \mathbb{Z}_{p_r^{k_r}}$: every $\mathbb{Z}_n$ is a product of rings $\mathbb{Z}_{p^k}$ of prime-power size. For instance $\mathbb{Z}_{360} \cong \mathbb{Z}_8 \times \mathbb{Z}_9 \times \mathbb{Z}_5$, and the script checks that $a \mapsto (a \bmod 8, a \bmod 9, a \bmod 5)$ is a bijection.

Pairwise is the right condition, not merely that the moduli have no factor common to all. The numbers 6, 10 and 15 have no common factor, but each pair shares one. The congruences $x \equiv 1 \pmod 6$ and $x \equiv 0 \pmod{10}$ already contradict each other, since the first makes $x$ odd and the second even.

The same theorem for polynomials

Nothing in the proof used more about the integers than Bezout's identity and the divisibility lemma. Both hold for polynomials over a field (Polynomial Division over a Field). So the theorem holds in $F[x]$, with relatively prime polynomials as moduli.

Theorem. Let $F$ be a field and $f(x)$, $g(x)$ nonconstant, relatively prime polynomials in $F[x]$. Then $[h]_{fg} \mapsto ([h]_f, [h]_g)$ is an isomorphism from $F[x]/(fg)$ onto $F[x]/(f) \times F[x]/(g)$.

Proof. Well defined and a homomorphism. If $fg$ divides $h - h'$, then so do $f$ and $g$. Each coordinate is a reduction of classes, which respects sums and products by the same calculation as for integers.

One-to-one. If $f$ and $g$ both divide $h - h'$, write $h - h' = fk$. Then $g \mid fk$ with $\gcd(g, f) = 1$, so $g \mid k$ by the cancellation theorem for polynomials, and $fg \mid h - h'$.

Onto. Write $fu + gv = 1$. Then $e_1 = gv$ is congruent to 1 modulo $f$ and to 0 modulo $g$, and $e_2 = fu$ the other way round, so $h_1 e_1 + h_2 e_2$ is sent to $([h_1]_f, [h_2]_g)$. $\blacksquare$

The simplest case has linear moduli. Over $\mathbb{Z}_3$, $x^2 - 1 = (x - 1)(x + 1)$, and the class of a polynomial modulo $x - c$ is determined by its value at $c$ (the remainder theorem). So $\mathbb{Z}_3[x]/(x^2 - 1) \cong \mathbb{Z}_3 \times \mathbb{Z}_3$ by $[h] \mapsto (h(1), h(-1))$. The idempotents are $e_1 = 2 + 2x$, which is 1 at $x = 1$ and 0 at $x = -1 = 2$, and $e_2 = 2 + x$, which is 0 at 1 and 1 at 2. The script checks that they are idempotents with $e_1 e_2 = 0$ and $e_1 + e_2 = 1$, and that the map is a bijection respecting products.

Writing a polynomial as $h(1)\,e_1 + h(-1)\,e_2$ is Lagrange interpolation. The theorem for polynomials with distinct linear factors says that a polynomial of degree less than $k$ is determined by its values at $k$ points, and any values can occur. The ring $\mathbb{Z}_3[x]/(x^2 - 1)$ is the reducible-modulus kind, with zero divisors $[x - 1]$ and $[x + 1]$, and the isomorphism shows why: it is a product of two fields.

Check your understanding. Where does the isomorphism send the class of $x$? Rebuild $x$ from $e_1$ and $e_2$ to check.

The class of $x$ has value 1 at $x = 1$ and $-1 = 2$ at $x = 2$, so it goes to $(1, 2)$. Interpolating, $1 \cdot e_1 + 2 \cdot e_2 = (2 + 2x) + (4 + 2x) = 6 + 4x$, which is $x$ modulo 3. The script agrees.

Background and generalizations

The Sunzi suanjing is the earliest known source for problems of this kind. Its date is uncertain. The MacTutor biography of its author records proposed dates ranging from the third century BC to about the fifth century AD, with recent historians placing it between the third and fifth centuries AD (O'Connor and Robertson); Judson (2026, §16.5) gives the first century AD.

In ring theory the theorem has a version for any commutative ring with identity. The multiples of $m$ and $n$ are replaced by two ideals $I$ and $J$ with $I + J = R$, the analogue of Bezout's identity $ms + nt = 1$, and the conclusion is $R/(I \cap J) \cong R/I \times R/J$. Judson (2026, §16.7, Exercise 39) poses it as an exercise. Its proof uses the quotient rings and the first isomorphism theorem of the next unit, which turns the two proofs above into one: the map $R \to R/I \times R/J$ is onto by the idempotent argument and its kernel is $I \cap J$. The course text treats this version in its optional Chapter 14 (Hungerford, 2014, §14.3).

What we have learned

Bezout's identity splits 1 into two pieces, each 1 for one modulus and 0 for the other, and those pieces solve every system of congruences to relatively prime moduli. As rings, $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$ exactly when $\gcd(m, n) = 1$. The isomorphism explained the idempotent 36 of $\mathbb{Z}_{45}$, split computations into small pieces, and made Euler's $\varphi$ multiplicative; for polynomials it is Lagrange interpolation.

The copy of $\mathbb{Z}_5$ inside $\mathbb{Z}_{45}$, the multiples of 9, has a property that a general subring lacks: multiplying a multiple of 9 by any element of $\mathbb{Z}_{45}$ gives another multiple of 9. Subsets with that property are the ones a ring can be reduced modulo. What are they in general, and how many does $\mathbb{Z}_{45}$ have? The next unit, Ideals and Quotient Rings, begins with Ideals and Principal Ideal Domains, which finds all six of them.

References

  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.). Brooks/Cole, Cengage Learning. The course text: isomorphisms and homomorphisms of rings, and the comparison of $\mathbb{Z}_{12}$ with $\mathbb{Z}_3 \times \mathbb{Z}_4$, in §3.3; the Chinese remainder theorem for integers (§14.1), its applications (§14.2) and its version for rings (§14.3) in an optional chapter (cited from the section titles only). record · 44 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026). Free online at judsonbooks.org. §16.5: the system of two congruences (Lemma 16.5.1), the Chinese remainder theorem for pairwise relatively prime moduli, proved by induction (Theorem 16.5.3), arithmetic with residues for parallel computation (Example 16.5.5), and the attribution to Sun-tsŭ; §16.7, Exercise 39, the Chinese remainder theorem for rings with $I + J = R$; Theorem 9.2.9, $\mathbb{Z}_m \times \mathbb{Z}_n \cong \mathbb{Z}_{mn}$ as groups if and only if $\gcd(m, n) = 1$. record · 44 pages
  • Moriarty, K. (Ed.), Kaliski, B., Jonsson, J., and Rusch, A. (2016). PKCS #1: RSA Cryptography Specifications Version 2.2, RFC 8017. Internet Engineering Task Force. §3.2, the private key as $(p, q, d_P, d_Q, q_{\text{inv}})$; §5.1.2, the decryption primitive in that form, $m_1 = c^{d_P} \bmod p$, $m_2 = c^{d_Q} \bmod q$, $h = (m_1 - m_2)\,q_{\text{inv}} \bmod p$, $m = m_2 + qh$. record · 2 pages
  • O'Connor, J. J., and Robertson, E. F. Sun Zi. MacTutor History of Mathematics Archive, University of St Andrews. The remainder problem of the Sunzi suanjing with its multipliers 70, 21 and 15 and answer 23, and the range of proposed dates for the book. record