The Chinese Remainder Theorem and Its Applications — Systems of Congruences and Direct Products of Rings

We prove the Chinese remainder theorem as a ring isomorphism. We extend the result to the case where the moduli are not pairwise coprime, present Garner's algorithm, give a CRT-based proof of the multiplicativity of phi, and discuss applications in competitive programming.

Folio Official

March 1, 2026

1 Statement of the Chinese Remainder Theorem

Theorem 1 (Chinese remainder theorem (CRT)).

Let

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

be pairwise coprime positive integers (

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

for

i \neq = j

). Then the system of congruences

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}

Proof.

Existence. For each

i

, set

M_{i} = M / m_{i}

. Since

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

for

j \neq = i

, we have

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

, so by Bé

t_{i}

with

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

. Put

e_{i} = M_{i} t_{i}

. Then

e_{i} \equiv 1 (mod m_{i})

and, for

j \neq = i

m_{j} ∣ M_{i}

gives

e_{i} \equiv 0 (mod m_{j})

. Setting

x = \sum_{i = 1}^{k} a_{i} e_{i}

, we find

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

for each

i

Uniqueness. If

x_{1}, x_{2}

are both solutions, then

m_{i} ∣ (x_{1} - x_{2})

for every

i

. Since the

m_{i}

are pairwise coprime,

M = m_{1} m_{2} \dots m_{k} ∣ (x_{1} - x_{2})

, i.e.

x_{1} \equiv x_{2} (mod M)

. □

2 Algebraic Proof: The Ring Isomorphism

Theorem 2 (Ring-theoretic formulation of CRT).

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

are pairwise coprime and

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

, then the map

Φ : Z / M Z \sim Z / m_{1} Z \times Z / m_{2} Z \times \dots \times Z / m_{k} Z

defined by

Φ (\overset{x}{ˉ}) = (\overset{x}{ˉ}_{1}, \dots, \overset{x}{ˉ}_{k})

, where

\overset{x}{ˉ}_{i} = x mod m_{i}

, is a ring isomorphism.

Proof.

That

Φ

is a ring homomorphism is clear (it preserves sums and products).

Injectivity. If

Φ (\overset{x}{ˉ}) = \overset{ˉ}{0}

, then

m_{i} ∣ x

for all

i

. Since the

m_{i}

are pairwise coprime,

M ∣ x

, so

\overset{x}{ˉ} = \overset{ˉ}{0}

Z / M Z

Surjectivity. Set

M_{i} = M / m_{i}

. Since

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

, there exists

t_{i}

with

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

. Put

e_{i} = M_{i} t_{i}

. Then

e_{i} \equiv 1 (mod m_{i})

and

e_{i} \equiv 0 (mod m_{j})

for

j \neq = i

. For any

(a_{1}, \dots, a_{k})

, the element

x = \sum_{i = 1}^{k} a_{i} e_{i}

satisfies

Φ (\overset{x}{ˉ}) = (\overset{a}{ˉ}_{1}, \dots, \overset{a}{ˉ}_{k})

Since

Φ

is an injective map between finite sets of the same cardinality (

∣ Z / M Z ∣ = M = \prod m_{i}

), it is also surjective, hence bijective. □

3 Explicit Construction of Solutions

Example 3.

Solve

x \equiv 2 (mod 3)

x \equiv 3 (mod 5)

x \equiv 2 (mod 7)

. Here

M = 105

M_{1} = 35

M_{2} = 21

M_{3} = 15

. From

35 t_{1} \equiv 1 (mod 3)

we get

t_{1} = 2

. From

21 t_{2} \equiv 1 (mod 5)

we get

t_{2} = 1

. From

15 t_{3} \equiv 1 (mod 7)

we get

t_{3} = 1

. Therefore

x \equiv 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233 \equiv 23 (mod 105)

4 The General Case

Theorem 4.

The system

x \equiv a_{1} (mod m_{1})

x \equiv a_{2} (mod m_{2})

has a solution if and only if

g cd (m_{1}, m_{2}) ∣ (a_{1} - a_{2})

. When a solution exists, it is unique modulo

lcm (m_{1}, m_{2})

Proof.

Writing

x = a_{1} + m_{1} k

, the second congruence becomes

m_{1} k \equiv a_{2} - a_{1} (mod m_{2})

. By the solvability criterion for linear congruences, this has a solution if and only if

g cd (m_{1}, m_{2}) ∣ (a_{2} - a_{1})

. The solution is then unique modulo

m_{1} \cdot m_{2} / g cd (m_{1}, m_{2}) = lcm (m_{1}, m_{2})

. □

5 Garner's Algorithm

Remark 5.

Garner's algorithm expresses the CRT solution in a mixed-radix representation

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

, thereby avoiding arithmetic with the (potentially very large) product

M

. The coefficients

r_{i}

are computed sequentially:

r_{1} = a_{1} mod m_{1}

r_{2} = (a_{2} - r_{1}) \cdot m_{1}^{- 1} mod m_{2}

, and so forth. Since every step involves only arithmetic modulo

m_{i}

, the algorithm avoids multi-precision multiplication and is highly efficient.

6 Multiplicativity of $φ$ via CRT

Corollary 6.

g cd (m, n) = 1

, then

φ (mn) = φ (m) φ (n)

Proof.

Taking the groups of units in the ring isomorphism

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

gives

(Z / mn Z)^{*} ≅ (Z / m Z)^{*} \times (Z / n Z)^{*}

. Comparing cardinalities yields

φ (mn) = φ (m) φ (n)

. □

Remark 7.

The CRT is also a fundamental tool in competitive programming. By performing computations modulo several distinct primes

p_{1}, \dots, p_{k}

and then combining the results via CRT, one can recover exact values of large quantities or carry out modular arithmetic with respect to a product

M

Number Theory Algebra Textbook Chinese Remainder Theorem CRT

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 and Its Applications — Systems of Congruences and Direct Products of Rings

Folio Official

March 1, 2026

1 Statement of the Chinese Remainder Theorem

Theorem 1 (Chinese remainder theorem (CRT)).

Let

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

be pairwise coprime positive integers (

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

for

i \neq = j

). Then the system of congruences

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}

Proof.

Existence. For each

i

, set

M_{i} = M / m_{i}

. Since

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

for

j \neq = i

, we have

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

, so by Bé

t_{i}

with

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

. Put

e_{i} = M_{i} t_{i}

. Then

e_{i} \equiv 1 (mod m_{i})

and, for

j \neq = i

m_{j} ∣ M_{i}

gives

e_{i} \equiv 0 (mod m_{j})

. Setting

x = \sum_{i = 1}^{k} a_{i} e_{i}

, we find

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

for each

i

Uniqueness. If

x_{1}, x_{2}

are both solutions, then

m_{i} ∣ (x_{1} - x_{2})

for every

i

. Since the

m_{i}

are pairwise coprime,

M = m_{1} m_{2} \dots m_{k} ∣ (x_{1} - x_{2})

, i.e.

x_{1} \equiv x_{2} (mod M)

. □

2 Algebraic Proof: The Ring Isomorphism

Theorem 2 (Ring-theoretic formulation of CRT).

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

are pairwise coprime and

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

, then the map

Φ : Z / M Z \sim Z / m_{1} Z \times Z / m_{2} Z \times \dots \times Z / m_{k} Z

defined by

Φ (\overset{x}{ˉ}) = (\overset{x}{ˉ}_{1}, \dots, \overset{x}{ˉ}_{k})

, where

\overset{x}{ˉ}_{i} = x mod m_{i}

, is a ring isomorphism.

Proof.

That

Φ

is a ring homomorphism is clear (it preserves sums and products).

Injectivity. If

Φ (\overset{x}{ˉ}) = \overset{ˉ}{0}

, then

m_{i} ∣ x

for all

i

. Since the

m_{i}

are pairwise coprime,

M ∣ x

, so

\overset{x}{ˉ} = \overset{ˉ}{0}

Z / M Z

Surjectivity. Set

M_{i} = M / m_{i}

. Since

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

, there exists

t_{i}

with

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

. Put

e_{i} = M_{i} t_{i}

. Then

e_{i} \equiv 1 (mod m_{i})

and

e_{i} \equiv 0 (mod m_{j})

for

j \neq = i

. For any

(a_{1}, \dots, a_{k})

, the element

x = \sum_{i = 1}^{k} a_{i} e_{i}

satisfies

Φ (\overset{x}{ˉ}) = (\overset{a}{ˉ}_{1}, \dots, \overset{a}{ˉ}_{k})

Since

Φ

is an injective map between finite sets of the same cardinality (

∣ Z / M Z ∣ = M = \prod m_{i}

), it is also surjective, hence bijective. □

3 Explicit Construction of Solutions

Example 3.

Solve

x \equiv 2 (mod 3)

x \equiv 3 (mod 5)

x \equiv 2 (mod 7)

. Here

M = 105

M_{1} = 35

M_{2} = 21

M_{3} = 15

. From

35 t_{1} \equiv 1 (mod 3)

we get

t_{1} = 2

. From

21 t_{2} \equiv 1 (mod 5)

we get

t_{2} = 1

. From

15 t_{3} \equiv 1 (mod 7)

we get

t_{3} = 1

. Therefore

x \equiv 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233 \equiv 23 (mod 105)

4 The General Case

Theorem 4.

The system

x \equiv a_{1} (mod m_{1})

x \equiv a_{2} (mod m_{2})

has a solution if and only if

g cd (m_{1}, m_{2}) ∣ (a_{1} - a_{2})

. When a solution exists, it is unique modulo

lcm (m_{1}, m_{2})

Proof.

Writing

x = a_{1} + m_{1} k

, the second congruence becomes

m_{1} k \equiv a_{2} - a_{1} (mod m_{2})

. By the solvability criterion for linear congruences, this has a solution if and only if

g cd (m_{1}, m_{2}) ∣ (a_{2} - a_{1})

. The solution is then unique modulo

m_{1} \cdot m_{2} / g cd (m_{1}, m_{2}) = lcm (m_{1}, m_{2})

. □

5 Garner's Algorithm

Remark 5.

Garner's algorithm expresses the CRT solution in a mixed-radix representation

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

, thereby avoiding arithmetic with the (potentially very large) product

M

. The coefficients

r_{i}

are computed sequentially:

r_{1} = a_{1} mod m_{1}

r_{2} = (a_{2} - r_{1}) \cdot m_{1}^{- 1} mod m_{2}

, and so forth. Since every step involves only arithmetic modulo

m_{i}

, the algorithm avoids multi-precision multiplication and is highly efficient.

6 Multiplicativity of $φ$ via CRT

Corollary 6.

g cd (m, n) = 1

, then

φ (mn) = φ (m) φ (n)

Proof.

Taking the groups of units in the ring isomorphism

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

gives

(Z / mn Z)^{*} ≅ (Z / m Z)^{*} \times (Z / n Z)^{*}

. Comparing cardinalities yields

φ (mn) = φ (m) φ (n)

. □

Remark 7.

The CRT is also a fundamental tool in competitive programming. By performing computations modulo several distinct primes

p_{1}, \dots, p_{k}

and then combining the results via CRT, one can recover exact values of large quantities or carry out modular arithmetic with respect to a product

M

Number Theory Algebra Textbook Chinese Remainder Theorem CRT

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 and Its Applications — Systems of Congruences and Direct Products of Rings

1 Statement of the Chinese Remainder Theorem

2 Algebraic Proof: The Ring Isomorphism

3 Explicit Construction of Solutions

4 The General Case

5 Garner's Algorithm

6 Multiplicativity of $φ$ via CRT

Share your expertise with the world

More from Folio Official

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

The Chinese Remainder Theorem and Its Applications — Systems of Congruences and Direct Products of Rings

1 Statement of the Chinese Remainder Theorem

2 Algebraic Proof: The Ring Isomorphism

3 Explicit Construction of Solutions

4 The General Case

5 Garner's Algorithm

6 Multiplicativity of $φ$ via CRT

Share your expertise with the world

More from Folio Official

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

1 Statement of the Chinese Remainder Theorem

2 Algebraic Proof: The Ring Isomorphism

3 Explicit Construction of Solutions

4 The General Case

5 Garner's Algorithm

6 Multiplicativity ofφvia CRT

Share your expertise with the world

More from Folio Official

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

1 Statement of the Chinese Remainder Theorem

2 Algebraic Proof: The Ring Isomorphism

3 Explicit Construction of Solutions

4 The General Case

5 Garner's Algorithm

6 Multiplicativity ofφvia CRT

Share your expertise with the world

More from Folio Official

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

6 Multiplicativity of $φ$ via CRT

6 Multiplicativity of $φ$ via CRT