Chinese Remainder Theorem — Definition, Formula & Examples

The Chinese Remainder Theorem (CRT) states that if you have a system of congruences with pairwise coprime moduli, there is exactly one solution modulo the product of those moduli. In other words, knowing the remainders when a number is divided by several coprime divisors uniquely determines its remainder when divided by their product.

Let $m_1, m_2, \ldots, m_k$ be pairwise coprime positive integers (i.e., $\gcd(m_i, m_j) = 1$ for $i \neq j$ ), and let $a_1, a_2, \ldots, a_k$ be arbitrary integers. Then the system $x \equiv a_i \pmod{m_i}$ for $i = 1, \ldots, k$ has a unique solution modulo $M = m_1 m_2 \cdots m_k$ .

Key Formula

x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}

Where:

$M$ = Product of all moduli: $M = m_1 m_2 \cdots m_k$
$M_i$ = Partial product $M / m_i$
$y_i$ = Modular inverse of $M_i$ modulo $m_i$, so $M_i y_i \equiv 1 \pmod{m_i}$
$a_i$ = The given remainder in the $i$-th congruence

How It Works

To solve a CRT system, compute

M = m_1 m_2 \cdots m_k

. For each

i

, let

M_i = M / m_i

. Find

y_i

such that

M_i y_i \equiv 1 \pmod{m_i}

(the modular inverse of

M_i

mod

m_i

). The solution is then

x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}

. Each term

a_i M_i y_i

is constructed so that it contributes the correct remainder mod

m_i

and contributes zero mod every other

m_j

Worked Example

Problem: Find x such that x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7).

Step 1: Compute the product of all moduli.

M = 3 \times 5 \times 7 = 105

Step 2: Compute each partial product

M_i

M_1 = 105/3 = 35, \quad M_2 = 105/5 = 21, \quad M_3 = 105/7 = 15

Step 3: Find the modular inverses. We need

35 y_1 \equiv 1 \pmod{3}

, so

y_1 = 2

since

35 \times 2 = 70 \equiv 1 \pmod{3}

. Similarly,

21 y_2 \equiv 1 \pmod{5}

gives

y_2 = 1

, and

15 y_3 \equiv 1 \pmod{7}

gives

y_3 = 1

since

15 \equiv 1 \pmod{7}

y_1 = 2, \quad y_2 = 1, \quad y_3 = 1

Step 4: Combine using the CRT formula.

x \equiv 2(35)(2) + 3(21)(1) + 2(15)(1) = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}

Answer:

x \equiv 23 \pmod{105}

. You can verify:

23 = 7 \times 3 + 2

23 = 4 \times 5 + 3

, and

23 = 3 \times 7 + 2

Why It Matters

CRT is foundational in cryptography — the RSA algorithm uses it to speed up decryption by working modulo smaller primes separately. It also appears in coding theory, computer science (e.g., efficient large-integer arithmetic), and abstract algebra when characterizing direct products of rings.

Common Mistakes

Mistake: Applying CRT when the moduli are not pairwise coprime.

Correction: The theorem requires

\gcd(m_i, m_j) = 1

for all

i \neq j

. If moduli share a common factor, the system may have no solution or require a generalized version of CRT.