Chinese Remainder Theorem

Simultaneous congruences — if moduli are coprime, there's a unique solution mod their product

Adjust the controls to solve a system of congruences
3
2
5
3
7
2
x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂) ⟹ x = Σ rᵢMᵢyᵢ (mod M), M = Πmᵢ

The CRT establishes a ring isomorphism ℤ/MZ ≅ ℤ/m₁ℤ × ℤ/m₂ℤ × ... × ℤ/mₖℤ when the mᵢ are pairwise coprime. Used in RSA cryptography (CRT speedup), calendar computations, error-correcting codes, and polynomial interpolation.