Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 37 · Modular Arithmetic and CRT

The Chinese Remainder Theorem

Solve systems of congruences with pairwise coprime moduli using the Chinese remainder theorem. Learn the proof, the constructive formula and how to code it.

A general counts his soldiers by lining them up in rows of 3, 5 and 7 and noting the leftovers: 2, 3 and 2. From those three small remainders he can recover the total, as long as the army has fewer than 105 soldiers. This puzzle appears in the Chinese text Sunzi Suanjing roughly 1,700 years ago, and the general result is the Chinese Remainder Theorem (CRT).

The theorem says that a number is determined by its remainders modulo several pairwise coprime numbers. It lets you break one big modulus into small pieces, compute in each piece, and glue the answers back together.

Statement

Theorem (CRT). Let m₁, m₂, ..., mₖ be pairwise coprime positive integers and let M = m₁m₂···mₖ. For any integers a₁, ..., aₖ the system

x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ)

has a solution, and the solution is unique modulo M.

Proof for two congruences

Take x ≡ a (mod m) and x ≡ b (mod n) with gcd(m, n) = 1. By Bezout, mu + nv = 1 for some integers u and v. Put

x = a·nv + b·mu.

Modulo m: the term b·mu vanishes, and nv ≡ 1 (since nv = 1 − mu), so x ≡ a. Modulo n: the term a·nv vanishes and mu ≡ 1, so x ≡ b. So x is a solution. For uniqueness, if x and x' are both solutions, then m | (x − x') and n | (x − x'); since m and n are coprime, mn | (x − x'). ∎

The general formula

For k congruences, let Mᵢ = M / mᵢ. Since the moduli are pairwise coprime, gcd(Mᵢ, mᵢ) = 1, so Mᵢ has an inverse yᵢ modulo mᵢ. Then

x = a₁M₁y₁ + a₂M₂y₂ + ... + aₖMₖyₖ (mod M).

Why it works: Mⱼ is a multiple of mᵢ for every j ≠ i, so in the sum only the i-th term survives modulo mᵢ, and it equals aᵢ · (Mᵢyᵢ) ≡ aᵢ · 1.

Python The soldiers puzzle

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer is x ≡ 23 (mod 105), so with fewer than 105 soldiers there are exactly 23.

A bijection, not just a solution

CRT says that the map x mod M ⟼ (x mod m₁, ..., x mod mₖ) is a one-to-one correspondence between ℤ/Mℤ and the product ℤ/m₁ℤ × ... × ℤ/mₖℤ. Addition and multiplication carry across componentwise. So computing mod M is equivalent to computing mod each mᵢ separately, then reconstructing.

Python Compute in the pieces, glue back

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Application: multiplicativity of φ

For coprime m and n, a residue x mod mn is coprime to mn exactly when it is coprime to m and to n. Under CRT, x corresponds to (x mod m, x mod n), and x is a unit mod mn exactly when each component is a unit. So the units mod mn correspond to pairs (unit mod m, unit mod n), and φ(mn) = φ(m)φ(n). That is the proof promised earlier.

Python Units correspond to pairs of units

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Application: speeding up computation (RSA-CRT)

To compute aᵉ mod pq, compute aᵉ mod p and aᵉ mod q separately (with the exponent reduced mod p − 1 and q − 1) and combine with CRT. The numbers involved are half as long, which makes RSA decryption about four times faster in practice.

Python Modular exponentiation through CRT

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two lines combine the pieces in a way that avoids multiplying large numbers; the next lesson explains this method, called Garner's algorithm.

Real-life uses

  • Calendars and cycles: an event repeating every 4 days and another every 9 days align on a unique day in each 36-day span.
  • Big-number arithmetic: represent a huge integer by its remainders modulo several machine-word primes and add or multiply component-wise.
  • Secret sharing: Asmuth–Bloom schemes hide a secret in remainders.
  • Counting: it splits counting problems mod n = p·q into counting mod p and mod q.

CRT in one picture

Split Replace x by its remainders.
Work Compute in each small modulus.
Glue Rebuild x mod the product.

Needs pairwise coprime moduli.

1 / 2

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Solve x = 2 (mod 3), x = 3 (mod 5). What is x modulo 15?

    8 mod 3 = 2 and 8 mod 5 = 3.
  2. 2. What condition does the basic CRT require on the moduli?

    Pairwise coprime moduli guarantee the inverses and the uniqueness modulo their product.
  3. 3. In the formula x = sum of a_i M_i y_i, what is y_i?

    M_i * y_i = 1 (mod m_i) and is 0 modulo every other modulus.
  4. 4. Why does RSA decryption use CRT?

    Working modulo p and q separately is much faster than one modulo n.

Summary

  • CRT: for pairwise coprime moduli, the system x ≡ aᵢ (mod mᵢ) has a unique solution modulo M = ∏ mᵢ.
  • Construct it as x = Σ aᵢ Mᵢ yᵢ with Mᵢ = M/mᵢ and yᵢ = Mᵢ⁻¹ mod mᵢ.
  • The map x → (x mod m₁, ..., x mod mₖ) is a bijection that respects + and ×.
  • It proves φ(mn) = φ(m)φ(n) and speeds up RSA.

Next: CRT for Non-Coprime Moduli and Garner's Algorithm