The Chinese Remainder Theorem: why simultaneous congruences can be merged

We view CRT as the number-theoretic incarnation of divide-and-conquer, prove the ring isomorphism Z/mnZ = Z/mZ x Z/nZ, and show how Garner's algorithm avoids overflow in practice.

Folio Official

March 1, 2026

The Chinese Remainder Theorem (CRT), whose origins trace back to the third-century Chinese mathematical text Sunzi Suanjing, remains a powerful tool in modern cryptography and competitive programming alike. It asserts that a system of congruences with pairwise coprime moduli can be "merged" into a single congruence – and the algebra behind this merging reveals a surprisingly clean structure.

1 The problem of Master Sun

Example 1 (From the Sunzi Suanjing).

A certain number leaves remainder

2

when divided by

3

, remainder

3

when divided by

5

, and remainder

2

when divided by

7

. What is the number?

In other words, solve the system

x \equiv 2 (mod 3), x \equiv 3 (mod 5), x \equiv 2 (mod 7) .

The answer is

x \equiv 23 (mod 105)

(where

105 = 3 \times 5 \times 7

2 The theorem

Theorem 2 (Chinese Remainder Theorem).

Let

m_{1}, m_{2}, \dots, m_{k}

be pairwise coprime (that is,

g cd (m_{i}, m_{j}) = 1

for

i \neq = j

). Then the system

x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{k} (mod m_{k})

has a unique solution modulo

M = m_{1} m_{2} \dots m_{k}

Remark 3.

In one sentence, the CRT says: the remainders modulo pairwise coprime integers carry exactly the same information as the single remainder modulo their product.

3 A constructive proof

Proof.

Set

M = m_{1} m_{2} \dots m_{k}

and

M_{i} = M / m_{i}

. Since

M_{i}

is the product of all moduli except

m_{i}

, and the moduli are pairwise coprime,

g cd (M_{i}, m_{i}) = 1

. By the extended Euclidean algorithm, there exists

t_{i}

with

M_{i} t_{i} \equiv 1 (mod m_{i})

Define

x = i = 1 \sum k a_{i} M_{i} t_{i} .

For each

i

: when

j \neq = i

m_{i} ∣ M_{j}

, so

M_{j} t_{j} \equiv 0 (mod m_{i})

. Meanwhile

M_{i} t_{i} \equiv 1 (mod m_{i})

. Therefore

x \equiv a_{i} \cdot 1 + j \neq = i \sum a_{j} \cdot 0 = a_{i} (mod m_{i}) .

For uniqueness: if

x

and

x^{'}

are both solutions, then

m_{i} ∣ (x - x^{'})

for every

i

. Since the

m_{i}

are pairwise coprime,

M ∣ (x - x^{'})

, so

x \equiv x^{'} (mod M)

. □

Example 4 (Solving Master Sun's problem).

m_{1} = 3

m_{2} = 5

m_{3} = 7

;

M = 105

$M_{1} = 35$ ; $35 t_{1} \equiv 1 (mod 3)$ gives $t_{1} = 2$ (since $35 \times 2 = 70 \equiv 1 (mod 3)$ ).
$M_{2} = 21$ ; $21 t_{2} \equiv 1 (mod 5)$ gives $t_{2} = 1$ (since $21 \equiv 1 (mod 5)$ ).
$M_{3} = 15$ ; $15 t_{3} \equiv 1 (mod 7)$ gives $t_{3} = 1$ (since $15 \equiv 1 (mod 7)$ ).

x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233 \equiv 23 (mod 105)

4 The ring-theoretic meaning: a direct product decomposition

The CRT has a clean algebraic formulation.

Theorem 5 (Ring isomorphism).

g cd (m, n) = 1

, there is a ring isomorphism

Z / mn Z ≅ Z / m Z \times Z / n Z,

given by

x mod mn \mapsto (x mod m, x mod n)

Remark 6.

This isomorphism says that "the remainder modulo

mn

" and "the pair of remainders modulo

m

and modulo

n

" carry exactly the same information. The

mn

possible remainders on the left correspond one-to-one with the

m \times n

pairs of remainders on the right.

This is the number-theoretic incarnation of divide and conquer: break a computation modulo the large number

mn

into two smaller computations modulo

m

and modulo

n

, then combine the results.

5 Garner's algorithm

The direct formula from the constructive proof involves the quantities $M_{i}$ , which can be astronomically large and prone to overflow. Garner's algorithm avoids this problem.

Remark 7 (Garner's idea).

Represent

x

in a mixed-radix form:

x = r_{1} + r_{2} m_{1} + r_{3} m_{1} m_{2} + \dots + r_{k} m_{1} m_{2} \dots m_{k - 1} .

Determine the coefficients

r_{1}, r_{2}, \dots, r_{k}

one at a time:

From $x \equiv a_{1} (mod m_{1})$ : $r_{1} = a_{1} mod m_{1}$ .
Substituting $x = r_{1} + r_{2} m_{1} + \dots$ into $x \equiv a_{2} (mod m_{2})$ gives $r_{2} m_{1} \equiv a_{2} - r_{1} (mod m_{2})$ , so $r_{2} \equiv (a_{2} - r_{1}) m_{1}^{- 1} (mod m_{2})$ .
Each subsequent $r_{i}$ is computed modulo $m_{i}$ in the same fashion.

Because every step operates modulo

m_{i}

, the intermediate values remain small.

6 Applications in competitive programming

Example 8 (Combining results from different prime moduli).

Suppose we want

(k n) mod m

where

m = p_{1} p_{2}

is not prime. Compute

(k n) mod p_{1}

and

(k n) mod p_{2}

separately, then merge them via CRT to obtain the answer modulo

m

Remark 9 (Typical patterns).

The CRT is applicable in the following common scenarios:

Combining results computed under several prime moduli into a single answer.
Recovering a very large number from its residues modulo several small moduli.
Handling a non-prime modulus by factoring it and computing modulo each prime factor.

7 Takeaway

The CRT establishes a one-to-one correspondence between a remainder modulo the product and a tuple of remainders modulo the individual (pairwise coprime) factors.
Algebraically, $Z / mn Z ≅ Z / m Z \times Z / n Z$ – the algebraic incarnation of divide and conquer.
The constructive proof gives an explicit formula for the solution.
Garner's algorithm avoids overflow by computing in a mixed-radix representation.

In the next article, we step into the world of quadratic residues and ask why exactly half of the nonzero elements modulo a prime are perfect squares.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The Chinese Remainder Theorem: why simultaneous congruences can be merged

We view CRT as the number-theoretic incarnation of divide-and-conquer, prove the ring isomorphism Z/mnZ = Z/mZ x Z/nZ, and show how Garner's algorithm avoids overflow in practice.

Folio Official

March 1, 2026

1 The problem of Master Sun

Example 1 (From the Sunzi Suanjing).

A certain number leaves remainder

2

when divided by

3

, remainder

3

when divided by

5

, and remainder

2

when divided by

7

. What is the number?

In other words, solve the system

x \equiv 2 (mod 3), x \equiv 3 (mod 5), x \equiv 2 (mod 7) .

The answer is

x \equiv 23 (mod 105)

(where

105 = 3 \times 5 \times 7

2 The theorem

Theorem 2 (Chinese Remainder Theorem).

Let

m_{1}, m_{2}, \dots, m_{k}

be pairwise coprime (that is,

g cd (m_{i}, m_{j}) = 1

for

i \neq = j

). Then the system

x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{k} (mod m_{k})

has a unique solution modulo

M = m_{1} m_{2} \dots m_{k}

Remark 3.

In one sentence, the CRT says: the remainders modulo pairwise coprime integers carry exactly the same information as the single remainder modulo their product.

3 A constructive proof

Proof.

Set

M = m_{1} m_{2} \dots m_{k}

and

M_{i} = M / m_{i}

. Since

M_{i}

is the product of all moduli except

m_{i}

, and the moduli are pairwise coprime,

g cd (M_{i}, m_{i}) = 1

. By the extended Euclidean algorithm, there exists

t_{i}

with

M_{i} t_{i} \equiv 1 (mod m_{i})

Define

x = i = 1 \sum k a_{i} M_{i} t_{i} .

For each

i

: when

j \neq = i

m_{i} ∣ M_{j}

, so

M_{j} t_{j} \equiv 0 (mod m_{i})

. Meanwhile

M_{i} t_{i} \equiv 1 (mod m_{i})

. Therefore

x \equiv a_{i} \cdot 1 + j \neq = i \sum a_{j} \cdot 0 = a_{i} (mod m_{i}) .

For uniqueness: if

x

and

x^{'}

are both solutions, then

m_{i} ∣ (x - x^{'})

for every

i

. Since the

m_{i}

are pairwise coprime,

M ∣ (x - x^{'})

, so

x \equiv x^{'} (mod M)

. □

Example 4 (Solving Master Sun's problem).

m_{1} = 3

m_{2} = 5

m_{3} = 7

;

M = 105

$M_{1} = 35$ ; $35 t_{1} \equiv 1 (mod 3)$ gives $t_{1} = 2$ (since $35 \times 2 = 70 \equiv 1 (mod 3)$ ).
$M_{2} = 21$ ; $21 t_{2} \equiv 1 (mod 5)$ gives $t_{2} = 1$ (since $21 \equiv 1 (mod 5)$ ).
$M_{3} = 15$ ; $15 t_{3} \equiv 1 (mod 7)$ gives $t_{3} = 1$ (since $15 \equiv 1 (mod 7)$ ).

x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233 \equiv 23 (mod 105)

4 The ring-theoretic meaning: a direct product decomposition

The CRT has a clean algebraic formulation.

Theorem 5 (Ring isomorphism).

g cd (m, n) = 1

, there is a ring isomorphism

Z / mn Z ≅ Z / m Z \times Z / n Z,

given by

x mod mn \mapsto (x mod m, x mod n)

Remark 6.

This isomorphism says that "the remainder modulo

mn

" and "the pair of remainders modulo

m

and modulo

n

" carry exactly the same information. The

mn

possible remainders on the left correspond one-to-one with the

m \times n

pairs of remainders on the right.

This is the number-theoretic incarnation of divide and conquer: break a computation modulo the large number

mn

into two smaller computations modulo

m

and modulo

n

, then combine the results.

5 Garner's algorithm

The direct formula from the constructive proof involves the quantities $M_{i}$ , which can be astronomically large and prone to overflow. Garner's algorithm avoids this problem.

Remark 7 (Garner's idea).

Represent

x

in a mixed-radix form:

x = r_{1} + r_{2} m_{1} + r_{3} m_{1} m_{2} + \dots + r_{k} m_{1} m_{2} \dots m_{k - 1} .

Determine the coefficients

r_{1}, r_{2}, \dots, r_{k}

one at a time:

From $x \equiv a_{1} (mod m_{1})$ : $r_{1} = a_{1} mod m_{1}$ .
Substituting $x = r_{1} + r_{2} m_{1} + \dots$ into $x \equiv a_{2} (mod m_{2})$ gives $r_{2} m_{1} \equiv a_{2} - r_{1} (mod m_{2})$ , so $r_{2} \equiv (a_{2} - r_{1}) m_{1}^{- 1} (mod m_{2})$ .
Each subsequent $r_{i}$ is computed modulo $m_{i}$ in the same fashion.

Because every step operates modulo

m_{i}

, the intermediate values remain small.

6 Applications in competitive programming

Example 8 (Combining results from different prime moduli).

Suppose we want

(k n) mod m

where

m = p_{1} p_{2}

is not prime. Compute

(k n) mod p_{1}

and

(k n) mod p_{2}

separately, then merge them via CRT to obtain the answer modulo

m

Remark 9 (Typical patterns).

The CRT is applicable in the following common scenarios:

Combining results computed under several prime moduli into a single answer.
Recovering a very large number from its residues modulo several small moduli.
Handling a non-prime modulus by factoring it and computing modulo each prime factor.

7 Takeaway

The CRT establishes a one-to-one correspondence between a remainder modulo the product and a tuple of remainders modulo the individual (pairwise coprime) factors.
Algebraically, $Z / mn Z ≅ Z / m Z \times Z / n Z$ – the algebraic incarnation of divide and conquer.
The constructive proof gives an explicit formula for the solution.
Garner's algorithm avoids overflow by computing in a mixed-radix representation.

In the next article, we step into the world of quadratic residues and ask why exactly half of the nonzero elements modulo a prime are perfect squares.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The Chinese Remainder Theorem: why simultaneous congruences can be merged

1 The problem of Master Sun

2 The theorem

3 A constructive proof

4 The ring-theoretic meaning: a direct product decomposition

5 Garner's algorithm

6 Applications in competitive programming

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

What does it mean to "divide evenly"? Why number theory begins with mod

Number theory meets cryptography: why RSA works and what makes it secure

The Chinese Remainder Theorem: why simultaneous congruences can be merged

1 The problem of Master Sun

2 The theorem

3 A constructive proof

4 The ring-theoretic meaning: a direct product decomposition

5 Garner's algorithm

6 Applications in competitive programming

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

What does it mean to "divide evenly"? Why number theory begins with mod

Number theory meets cryptography: why RSA works and what makes it secure