Simultaneous Congruences and Chinese Remainder Theorem

Core Idea

The Chinese Remainder Theorem (CRT) solves systems of linear congruences when moduli are pairwise coprime. The theorem guarantees a unique solution modulo the product of moduli and provides a constructive method for finding it, with applications in cryptography.

Explainer

From linear congruences, you know how to solve a single equation of the form ax ≡ b (mod m). The Chinese Remainder Theorem (CRT) lets you solve several such equations *simultaneously*. The classic ancient puzzle: find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. The pairwise coprime condition on the moduli (gcd of any two is 1) is what makes CRT work — when moduli share factors, the system may have no solution or infinitely many in an uncontrolled way.

The theorem's guarantee is striking: if the moduli m₁, m₂, …, mₖ are pairwise coprime, then any system of congruences x ≡ aᵢ (mod mᵢ) has exactly one solution modulo M = m₁m₂⋯mₖ. This means the solution space is not just nonempty — it is precisely one residue class within a predictable range. The constructive proof turns this existence claim into an algorithm. For each i, let Mᵢ = M/mᵢ (the product of all moduli except mᵢ). Because mᵢ and Mᵢ are coprime, the modular inverse of Mᵢ modulo mᵢ exists — and this is exactly where the Euclidean algorithm from your prerequisites enters. Call that inverse yᵢ. Then x = Σ aᵢMᵢyᵢ (mod M) is the unique solution.

Working through the puzzle: M = 3 × 5 × 7 = 105. For the first congruence (mod 3): M₁ = 35, and 35 ≡ 2 (mod 3), so the inverse of 2 mod 3 is 2 (since 2 × 2 = 4 ≡ 1). Contribution: 2 × 35 × 2 = 140. Repeat for the others and sum mod 105 to get 23. Verify: 23 = 7 × 3 + 2 ✓, 23 = 4 × 5 + 3 ✓, 23 = 3 × 7 + 2 ✓.

CRT is not just a number puzzle — it is a structural decomposition theorem. It says that computing modulo M = m₁m₂⋯mₖ (with coprime factors) is exactly equivalent to computing modulo each mᵢ independently and reassembling. This decomposition is the backbone of fast arithmetic in cryptography: rather than doing one giant modular multiplication, you do several smaller ones in parallel and combine. The theorem also appears in computer science (hash tables, polynomial interpolation) and signal processing, always carrying the same idea: a complicated global problem decomposes cleanly into independent local pieces when the right coprimality structure is present.