Chinese Remainder Theorem Calculator
Solve a system of simultaneous congruences with pairwise coprime moduli via CRT.
Inputs
The remainder values a₁, a₂, … in x ≡ aᵢ (mod mᵢ).
Pairwise coprime moduli m₁, m₂, …
Smallest Positive Solution
23
Combined Modulus (M)
105
General Solution
x ≡ 23 (mod 105)
Step by step
Product of moduli
M = 3 × 5 × 7 = 105
Term 1
a1×M1×y1 = 2×35×2
Term 2
a2×M2×y2 = 3×21×1
Term 3
a3×M3×y3 = 2×15×1
Sum mod M
= 23
General solution
x = 23 + 105k for any integer k
How it works
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).
Formula
CRT solution
x = Σ(aᵢ × Mᵢ × yᵢ) mod M, where Mᵢ = M/mᵢ and yᵢ = Mᵢ⁻¹ mod mᵢ
- aᵢ
- Remainder for ith congruence
- mᵢ
- ith modulus
- M
- Product of all moduli
- yᵢ
- Modular inverse of Mᵢ mod mᵢ
Frequently Asked Questions
What does 'pairwise coprime' mean?
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.
What if the moduli are not coprime?
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.