Chinese Remainder Theorem

Congruences: x ≡ r_i (mod m_i)

Modulus m₁: 3 Remainder r₁ (mod m₁): 1 Modulus m₂: 5 Remainder r₂ (mod m₂): 3 Modulus m₃: 7 Remainder r₃ (mod m₃): 2

Solution & Reconstruction

Chinese Remainder Theorem (CRT): If m₁, m₂, ..., m_k are pairwise coprime, then for any remainders r₁,...,r_k, there exists a unique x ∈ [0, M) (where M = ∏m_i) satisfying x ≡ r_i (mod m_i) simultaneously. Construction: For each i, compute M_i = M/m_i, then find y_i = M_i⁻¹ (mod m_i) (modular inverse). Solution: x = (∑ r_i · M_i · y_i) mod M. Cryptographic applications: RSA-CRT decryption (Garner's algorithm) speeds up modular exponentiation by ~4×. Secret sharing: encode secret as x, distribute residues as shares. The grid visualization shows which integers satisfy each congruence — the intersection is the CRT solution.

Chinese Remainder Theorem — Modular Arithmetic

Congruences: x ≡ r_i (mod m_i)

Solution & Reconstruction