Solve a system of simultaneous congruences with pairwise coprime moduli via CRT.
The Chinese Remainder Theorem (CRT) states that if m₁, m₂, …, mₖ are pairwise coprime, then the system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ aₖ (mod mₖ) has a unique solution modulo M = m₁×m₂×…×mₖ. The solution is constructed by computing partial products Mᵢ = M/mᵢ, finding their modular inverses yᵢ (mod mᵢ), and summing x = Σ aᵢ×Mᵢ×yᵢ (mod M).
CRT solution
x = Σ(aᵢ × Mᵢ × yᵢ) mod M, where Mᵢ = M/mᵢ and yᵢ = Mᵢ⁻¹ mod mᵢ
Every pair of moduli must have gcd = 1. For example, {3, 5, 7} is pairwise coprime because gcd(3,5)=1, gcd(3,7)=1, and gcd(5,7)=1. But {4, 6, 5} fails because gcd(4,6)=2.
The standard CRT does not apply. A generalized version exists that works when the system is consistent (each pair aᵢ ≡ aⱼ mod gcd(mᵢ, mⱼ)), but this calculator requires pairwise coprime moduli.