Chinese Remainder Theorem

Solve systems of linear congruences efficiently. Given remainders and moduli, find the unique solution modulo the product of all moduli.

Congruences
Equation 1

x ≡ 2 (mod 3)

Equation 2

x ≡ 3 (mod 5)

Equation 3

x ≡ 2 (mod 7)

What is CRT?

The Chinese Remainder Theorem states that if integers n₁, n₂, ..., nₖ are pairwise coprime, then for any sequence of integers a₁, a₂, ..., aₖ, there exists a unique solution modulo N = n₁ × n₂ × ... × nₖ.

Given: x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ aₖ (mod nₖ)
Find: x such that all congruences are satisfied

CRT Applications

Cryptography

Speeds up RSA decryption using modular decomposition.

Computing

Reduces large modulo operations to smaller ones.

Number Theory

Solves Diophantine equations efficiently.

How It Works

For a system like x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7):

Step 1: Compute M = 3 × 5 × 7 = 105

Step 2: For each congruence, compute M_i = M / n_i and find its modular inverse

Step 3: Combine: x = Σ(a_i × M_i × M_i⁻¹) mod 105

Result: x ≡ 17 (mod 105) (and any number 17 + 105k is also a solution)