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ᵢ.
Did our AI summary help? Let us know.
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.
Ready to run the numbers?
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.
Run the calculator when you are ready.
Enter Congruences
Moduli
Solution vs LCM
📐 Step-by-Step Breakdown
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.
Related Calculators
Inverse Modulo Calculator
Find the modular multiplicative inverse a^(-1) mod m using the Extended Euclidean Algorithm. Requires gcd(a,m)=1. Step-by-step solutions for cryptography...
MathematicsMultiplicative Inverse Modulo Calculator
Find the multiplicative inverse of a modulo m: a×x ≡ 1 (mod m). Uses the Extended Euclidean Algorithm with step-by-step trace. Applications in cryptography (RSA, Diffie-Hellman), linear congruences, and Chinese Remainder Theorem. Verify with Fermat's Little Theorem for prime moduli.
MathematicsExtended Euclidean Algorithm Calculator
Find gcd(a,b) and Bézout coefficients x, y such that ax + by = gcd(a,b). Step-by-step division table. Modular inverse, linear Diophantine equations.
MathematicsPower Mod Calculator
Compute a^b mod m (modular exponentiation) using the fast square-and-multiply algorithm. Essential for cryptography (RSA, Diffie-Hellman), number theory, and...
MathematicsConsecutive Integers Calculator
Find n consecutive integers that sum to a target, or compute sum and product of consecutive integers. Supports even and odd consecutive sequences....
MathematicsPerfect Square Calculator
Check if a number is a perfect square, find its square root, and explore nearby squares. Includes digit pattern analysis, prime factorization verification...
Mathematics