Chinese Remainder Theorem: Solving Congruence Systems
When moduli are pairwise coprime, the CRT guarantees a unique solution modulo their product. Given x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., we construct x = Σ aᵢMᵢyᵢ mod M, where M = Πmᵢ and yᵢ = Mᵢ⁻¹ mod mᵢ.
Why This Mathematical Concept Matters
Why: CRT answers: What number satisfies all these remainders? Essential in cryptography (RSA), calendar systems, and error-correcting codes. When moduli are coprime, the solution is unique modulo M.
How: Compute M = product of moduli. For each i: Mᵢ = M/mᵢ, find yᵢ = modular inverse of Mᵢ mod mᵢ. Then x = Σ aᵢMᵢyᵢ mod M.
- ●CRT requires pairwise coprime moduli: gcd(mᵢ,mⱼ)=1 for i≠j.
- ●Used in RSA: combine results mod p and mod q to get mod n=pq.
- ●Ancient Chinese used it for calendar calculations.
📐 Examples — Click to Load
Enter Congruences
⚠️For educational and informational purposes only. Verify with a qualified professional.
🧮 Fascinating Math Facts
RSA decryption uses CRT to speed up computation.
CRT requires pairwise coprime moduli for unique solution.
📋 Key Takeaways
- • CRT: Given x ≡ a_i (mod m_i) with pairwise coprime m_i, unique solution mod M
- • M = m_1 × m_2 × ... × m_n
- • Used in RSA, calendar systems, error-correcting codes
- • Solution form: x = x_0 + k×LCM for any integer k
💡 Did You Know?
📖 How It Works
For each i, compute M_i = M/m_i and y_i = inverse of M_i mod m_i. Then x = Σ a_i × M_i × y_i (mod M). The moduli must be pairwise coprime (GCD = 1) for a unique solution modulo M. If moduli share factors, check remainder consistency first.
📝 Worked Example: x≡2 mod 3, x≡3 mod 5
M = 3×5 = 15
M_1 = 15/3 = 5, y_1 = 5⁻¹ mod 3 = 2
M_2 = 15/5 = 3, y_2 = 3⁻¹ mod 5 = 2
x = 2×5×2 + 3×3×2 = 20 + 18 = 38 ≡ 8 (mod 15)
Verify: 8 mod 3 = 2 ✓, 8 mod 5 = 3 ✓
🚀 Real-World Applications
🔐 RSA
Speed up decryption: compute mod p and mod q, combine with CRT.
📅 Calendars
Combine cyclic systems (days, months).
📡 Error Correction
Reed-Solomon and similar codes.
🔢 Large Arithmetic
Residue number systems.
🎲 Hashing
Distributed systems, consistent hashing.
📐 Number Theory
Primality testing, factorization.
⚠️ Common Mistakes to Avoid
- Non-coprime moduli: Check GCD of each pair; inconsistent remainders → no solution.
- Wrong formula: Use M_i = M/m_i, not M_i = m_i.
- Forgetting to reduce: Final x should be in [0, M) or [0, LCM).
- Modular inverse fails: When gcd(M_i, m_i) ≠ 1, no inverse exists.
🎯 Expert Tips
💡 Verify
Plug solution back into each congruence.
💡 Non-Coprime
Check remainder consistency mod GCD first.
💡 LCM
Use LCM when moduli share factors.
💡 Modular Inverse
Inverse exists iff GCD(a, m) = 1.
📊 Reference Table
| System | Solution |
|---|---|
| x≡2 mod 3, x≡3 mod 5 | x≡8 mod 15 |
| x≡1 mod 2, x≡2 mod 3 | x≡5 mod 6 |
| x≡0 mod 2,3,5 | x≡0 mod 30 |
📐 Quick Reference
🎓 Practice Problems
❓ FAQ
What is CRT?
Theorem: system x ≡ a_i (mod m_i) with coprime m_i has unique solution mod M.
When does no solution exist?
When GCD(m_i,m_j) > 1 and remainders are inconsistent mod that GCD.
How is it used in RSA?
Decrypt by computing mod p and mod q separately, then combine with CRT.
What if moduli share factors?
Check consistency; solution modulo LCM may exist.
How to find modular inverse?
Extended Euclidean algorithm: find x such that a×x ≡ 1 (mod m).
What is the solution set?
All x = x_0 + k×LCM for integer k.
Verify?
Plug x into each congruence: x mod m_i should equal a_i.
📌 Summary
The Chinese Remainder Theorem solves systems of congruences x ≡ a_i (mod m_i) when moduli are pairwise coprime. Solution: x = Σ a_i × M_i × y_i (mod M). Used in RSA, calendars, and error correction.
✅ Verification Tip
Always verify: plug the solution into each congruence. x mod m_i should equal a_i for every i.
🔗 Next Steps
Try the Modulo Calculator, Inverse Modulo Calculator for modular inverses, or Extended Euclidean Algorithm for Bézout coefficients.
⚠️ Disclaimer: Results for educational use. Verify critical calculations independently.