Helpful context:

Here is a puzzle that appears in Sun Tzu’s Mathematical Manual, written around the 3rd to 5th century CE: “There are certain things whose number is unknown. When divided by 3, the remainder is 2; when divided by 5, the remainder is 3; when divided by 7, the remainder is 2. What is the number?” The answer is 23. But the real question is not what the number is - it is whether a number always exists, and whether it is unique.

This is the Chinese Remainder Theorem: given a system of congruences $x \equiv a_i \pmod{n_i}$ with pairwise coprime moduli, a solution exists and is unique modulo the product $N = n_1 n_2 \cdots n_k$. The theorem is more than a puzzle-solver. At the algebraic level, it says that when the moduli are coprime, the ring $\mathbb{Z}/N\mathbb{Z}$ is isomorphic to the product $\mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}$. Arithmetic modulo $N$ completely factors into independent arithmetic modulo each $n_i$. This structural decomposition has consequences throughout algebra, cryptography, and algorithm design.

The CRT converts a hard problem in a large ring into several easy problems in small rings. This principle - decompose, solve independently, recombine - recurs throughout mathematics and computer science. In RSA, it yields a 4x speedup in decryption. In algorithm design, it allows integer arithmetic to be parallelized over small moduli. In algebraic number theory, it is the foundation of the theory of ideals.

The Theorem

Theorem (Chinese Remainder Theorem). Let $n_1, n_2, \ldots, n_k$ be pairwise coprime positive integers (meaning $\gcd(n_i, n_j) = 1$ for all $i \neq j$), and let $a_1, a_2, \ldots, a_k$ be any integers. Then the system

$$x \equiv a_1 \pmod{n_1}, \quad x \equiv a_2 \pmod{n_2}, \quad \ldots, \quad x \equiv a_k \pmod{n_k}$$

has a solution, and any two solutions are congruent modulo $N = n_1 n_2 \cdots n_k$.

Proof of existence (constructive). Set $N = \prod_{i=1}^k n_i$ and $M_i = N / n_i$ (the product of all moduli except $n_i$).

Since $n_1, \ldots, n_k$ are pairwise coprime, we have $\gcd(M_i, n_i) = 1$ for each $i$ (since $M_i$ is a product of all $n_j$ with $j \neq i$, none of which share a factor with $n_i$). Therefore $M_i$ is invertible modulo $n_i$; let $y_i = M_i^{-1} \pmod{n_i}$.

Define

$$x = \sum_{i=1}^k a_i M_i y_i \pmod{N}.$$

We verify: for each fixed $j$,

$$x \equiv \sum_{i=1}^k a_i M_i y_i \pmod{n_j}.$$

For $i \neq j$: $M_i = N/n_i$ contains $n_j$ as a factor (since $j \neq i$), so $M_i \equiv 0 \pmod{n_j}$.

For $i = j$: $M_j y_j \equiv M_j \cdot M_j^{-1} \equiv 1 \pmod{n_j}$.

Therefore $x \equiv a_j \cdot 1 = a_j \pmod{n_j}$. Since $j$ was arbitrary, $x$ satisfies all congruences. $\square$

Proof of uniqueness. If $x$ and $x'$ are both solutions, then $x - x' \equiv 0 \pmod{n_i}$ for each $i$. Since the $n_i$ are pairwise coprime, $n_i \mid (x - x')$ for all $i$ implies $N \mid (x - x')$, so $x \equiv x' \pmod{N}$. $\square$

The Ring Isomorphism

The CRT has a deeper algebraic formulation.

Theorem. If $n_1, \ldots, n_k$ are pairwise coprime, then

$$\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}$$

as rings (preserving both addition and multiplication).

The isomorphism sends $x \pmod{N}$ to the tuple $(x \pmod{n_1}, x \pmod{n_2}, \ldots, x \pmod{n_k})$.

This is a ring homomorphism: $(x + y) \bmod n_i = (x \bmod n_i) + (y \bmod n_i)$, and similarly for multiplication. The CRT says it is bijective (the inverse is the constructive formula above).

The consequence: any computation in $\mathbb{Z}/N\mathbb{Z}$ can be decomposed into $k$ independent computations in the smaller rings $\mathbb{Z}/n_i\mathbb{Z}$. The components do not interact. This independence is what makes the theorem so powerful.

For instance, if $N = pq$ with $p, q$ prime and coprime, then $\mathbb{Z}/pq\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z}$. An element $x$ is a unit in $\mathbb{Z}/pq\mathbb{Z}$ if and only if it is a unit in both $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$, which recovers the formula $\phi(pq) = (p-1)(q-1)$.

Example: Solving the Puzzle

The original puzzle: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$.

Here $N = 3 \cdot 5 \cdot 7 = 105$, $M_1 = 35$, $M_2 = 21$, $M_3 = 15$.

  • $y_1 = 35^{-1} \pmod{3}$: since $35 \equiv 2 \pmod 3$, need $2y_1 \equiv 1 \pmod 3$, so $y_1 = 2$.
  • $y_2 = 21^{-1} \pmod{5}$: since $21 \equiv 1 \pmod 5$, $y_2 = 1$.
  • $y_3 = 15^{-1} \pmod{7}$: since $15 \equiv 1 \pmod 7$, $y_3 = 1$.

Then $x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \equiv 233 - 2 \cdot 105 = 23 \pmod{105}$.

Verification: $23 = 7 \cdot 3 + 2$ (remainder 2 mod 3), $23 = 4 \cdot 5 + 3$ (remainder 3 mod 5), $23 = 3 \cdot 7 + 2$ (remainder 2 mod 7). Correct.

Application: RSA with CRT

Standard RSA decryption computes $m = c^d \pmod{N}$ where $N = pq$. This requires modular exponentiation modulo a 2048-bit number, which is expensive.

The CRT speedup uses the ring isomorphism $\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z}$:

  1. Precompute $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$.
  2. Compute $m_p = c^{d_p} \bmod p$ and $m_q = c^{d_q} \bmod q$ independently.
  3. Combine using CRT to find $m \bmod N$ such that $m \equiv m_p \pmod p$ and $m \equiv m_q \pmod q$.

Step 2 is valid by Fermat’s Little Theorem: $c^d \equiv c^{d \bmod (p-1)} \pmod p$ for $\gcd(c,p) = 1$.

The speedup comes from working with 1024-bit numbers instead of 2048-bit numbers. Since modular exponentiation costs $O(k^2)$ in the number of bits $k$ (roughly), working modulo $p$ and $q$ separately costs $2 \cdot O((k/2)^2) = O(k^2/2)$ - a factor of 2 improvement each. Since we do two such computations (mod $p$ and mod $q$), the total cost is $O(k^2/2 + k^2/2) = O(k^2)$… but the key point is that the operand sizes are half as large at every step, making each multiplication faster. In practice the CRT gives approximately a 4x speedup in RSA decryption on modern hardware.

Application: Large Integer Arithmetic

For very large integer computations, the CRT allows arithmetic to be distributed across small moduli, avoiding big-integer multiplication entirely.

To multiply two large integers $A$ and $B$:

  1. Choose moduli $m_1, m_2, \ldots, m_k$ (small primes) with $N = m_1 \cdots m_k > 2AB$.
  2. Compute $a_i = A \bmod m_i$ and $b_i = B \bmod m_i$ for each $i$.
  3. Compute $c_i = a_i \cdot b_i \bmod m_i$ (small multiplication).
  4. Reconstruct $C = AB$ from $(c_i)$ using CRT.

This approach is useful in implementations of polynomial multiplication and FFT-based algorithms, where the moduli are chosen as “NTT-friendly” primes that support fast number-theoretic transforms.

Application: Reed-Solomon Codes

Reed-Solomon codes are error-correcting codes based on polynomial arithmetic over finite fields. Their analysis uses a polynomial version of the CRT.

Polynomial CRT. If $m_1(x), m_2(x), \ldots, m_k(x)$ are pairwise coprime polynomials over a field $F$, and $M(x) = m_1(x) \cdots m_k(x)$, then for any polynomials $a_1(x), \ldots, a_k(x)$, there is a unique $f(x) \pmod{M(x)}$ such that $f(x) \equiv a_i(x) \pmod{m_i(x)}$ for all $i$.

In Reed-Solomon encoding: the message is encoded as a polynomial $f(x)$ of degree $< k$. The codeword consists of evaluations $f(\alpha_1), f(\alpha_2), \ldots, f(\alpha_n)$ at $n$ distinct points. Each evaluation is a CRT residue: the moduli are $(x - \alpha_i)$, and the residue of $f(x)$ modulo $(x - \alpha_i)$ is $f(\alpha_i)$. Decoding recovers $f(x)$ from enough residues, exactly as CRT recovers an integer from its remainders.

Generalization

The CRT generalizes beyond $\mathbb{Z}$. The key hypothesis is not integrality but coprimality of the ideals involved.

Theorem (General CRT). Let $R$ be a commutative ring and $I_1, \ldots, I_k$ ideals with $I_i + I_j = R$ for all $i \neq j$ (the ideals are pairwise comaximal). Then

$$R / (I_1 \cap \cdots \cap I_k) \cong R/I_1 \times \cdots \times R/I_k.$$

In $\mathbb{Z}$, coprime ideals are exactly coprime integer moduli (since $(n) + (m) = (1) = \mathbb{Z}$ iff $\gcd(n,m) = 1$). In polynomial rings over a field, coprime polynomials generate the whole ring. In both cases, the structural theorem is the same.

Summary

Fact Statement
Existence Solution always exists when moduli are pairwise coprime
Uniqueness Solution is unique modulo $N = n_1 \cdots n_k$
Ring structure $\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}$
Constructive formula $x = \sum_i a_i M_i (M_i^{-1} \bmod n_i) \pmod{N}$
RSA application Decompose $c^d \bmod N$ into $c^{d_p} \bmod p$ and $c^{d_q} \bmod q$

Read next: