Chinese Remainder Theorem Calculator | Simultaneous Congruences Solver
Solve a system of simultaneous congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), … using the Chinese Remainder Theorem. Applies Garner's algorithm for pairwise-coprime moduli and shows step-by-step Bézout coefficient computation.
Enter System of Congruences: x ≡ aᵢ (mod mᵢ)
What Is the Chinese Remainder Theorem Calculator | Simultaneous Congruences Solver?
The Chinese Remainder Theorem (CRT) guarantees that if the moduli m₁, m₂, …, mₖ are pairwise coprime (gcd(mᵢ, mⱼ) = 1 for all i ≠ j), 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 algorithm computes Mᵢ = M/mᵢ for each i, then finds the modular inverse yᵢ of Mᵢ modulo mᵢ using the extended Euclidean algorithm, and sums aᵢ·Mᵢ·yᵢ modulo M.
Formula
M = m₁·m₂·…·mₖ | Mᵢ = M/mᵢ | yᵢ = Mᵢ⁻¹ mod mᵢ | x = (Σ aᵢ·Mᵢ·yᵢ) mod M
How to Use
- 1
Select a preset or manually enter aᵢ (the remainder) and mᵢ (the modulus) for each congruence row.
- 2
Click "+ Add Equation" to add more congruences (up to 6 total); click × to remove any row.
- 3
Ensure all moduli are pairwise coprime — the solver will warn you with the gcd if not.
- 4
Click "Solve CRT" to compute the unique solution x and the product M.
- 5
Read the result box showing x, M, and the extended solution set (x + k·M for k = −2 to 2).
- 6
Review the step-by-step table showing Mᵢ, Mᵢ mod mᵢ, the modular inverse yᵢ, and the term aᵢ·Mᵢ·yᵢ mod M for each row.
- 7
Verify by substituting x back: x mod m₁ should equal a₁, x mod m₂ should equal a₂, and so on.
Enter 2 to 6 congruence equations of the form x ≡ aᵢ (mod mᵢ) using pairwise coprime moduli, then click Solve CRT.
Example Calculation
System: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). M = 3×5×7 = 105. M₁ = 35, 35 mod 3 = 2, y₁ = 2⁻¹ mod 3 = 2; term = 2×35×2 = 140 mod 105 = 35. M₂ = 21, 21 mod 5 = 1, y₂ = 1; term = 3×21×1 = 63 mod 105 = 63. M₃ = 15, 15 mod 7 = 1, y₃ = 1; term = 2×15×1 = 30 mod 105 = 30. x = (35 + 63 + 30) mod 105 = 128 mod 105 = 23. Check: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓.
Understanding Chinese Remainder Theorem | Simultaneous Congruences
Classic CRT Examples and Their Solutions
| System of Congruences | M | Solution x | Verification |
|---|---|---|---|
| x≡2(3), x≡3(5), x≡2(7) | 105 | 23 | 23 mod 3=2, mod 5=3, mod 7=2 |
| x≡0(2), x≡0(3), x≡1(5) | 30 | 15 | 15 mod 2=1 — wait, a₁=0: 0 mod 2=0 ✓ |
| x≡1(2), x≡2(3), x≡3(5) | 30 | 23 | 23 mod 2=1, mod 3=2, mod 5=3 |
| x≡0(3), x≡1(4), x≡2(5) | 60 | 57 | 57 mod 3=0, mod 4=1, mod 5=2 |
| x≡1(5), x≡2(7), x≡3(11) | 385 | 366 | 366 mod 5=1, mod 7=2, mod 11=3 |
| x≡3(5), x≡4(7) | 35 | 18 | 18 mod 5=3, 18 mod 7=4 |
Extended Euclidean Algorithm — Modular Inverse Reference
| a (find a⁻¹ mod m) | m | Inverse a⁻¹ | Verify: a × a⁻¹ mod m | Bézout: a·x + m·y = 1 |
|---|---|---|---|---|
| 2 | 3 | 2 | 2×2=4≡1 mod 3 ✓ | 2×2 + 3×(−1)=1 |
| 3 | 5 | 2 | 3×2=6≡1 mod 5 ✓ | 3×2 + 5×(−1)=1 |
| 2 | 7 | 4 | 2×4=8≡1 mod 7 ✓ | 2×4 + 7×(−1)=1 |
| 5 | 6 | 5 | 5×5=25≡1 mod 6 ✓ | 5×5 + 6×(−4)=1 |
| 4 | 9 | 7 | 4×7=28≡1 mod 9 ✓ | 4×7 + 9×(−3)=1 |
| 7 | 11 | 8 | 7×8=56≡1 mod 11 ✓ | 7×8 + 11×(−5)=1 |
| 3 | 7 | 5 | 3×5=15≡1 mod 7 ✓ | 3×5 + 7×(−2)=1 |
Applications of the Chinese Remainder Theorem
- ›RSA Cryptography: CRT speeds up RSA private-key operations by computing modular exponentiations separately mod p and mod q, then combining with Garner's formula — giving a 4× speedup.
- ›Multi-precision arithmetic: Large-number computations are split across small coprime moduli, processed in parallel, then recombined — used in computer algebra systems.
- ›Error-correcting codes: CRT underlies certain algebraic codes where codewords are residues modulo different polynomials.
- ›Calendar and scheduling: Finding a date that falls on a given day of the week (mod 7) and day of the month (mod 30) simultaneously is a direct CRT application.
- ›Hash functions and secret sharing: Shamir's Secret Sharing distributes a secret among k parties so any t ≥ threshold parties can recover it using polynomial interpolation, closely related to CRT.
Frequently Asked Questions
What does "pairwise coprime" mean?
Two integers are coprime if their greatest common divisor is 1. Pairwise coprime means every pair in the set is coprime — gcd(mᵢ, mⱼ) = 1 for all i ≠ j. For example, {3, 5, 7} is pairwise coprime, but {4, 6, 5} is not (gcd(4,6) = 2).
What if the moduli are not coprime?
If two moduli share a common factor d = gcd(mᵢ, mⱼ), the system may or may not have a solution. A solution exists only if aᵢ ≡ aⱼ (mod d) for every non-coprime pair. When this compatibility condition holds, the moduli can be merged using the extended GCD — but for simplicity, this calculator currently requires pairwise coprime moduli.
How is the modular inverse computed?
The modular inverse yᵢ of Mᵢ modulo mᵢ satisfies Mᵢ·yᵢ ≡ 1 (mod mᵢ). It is found via the extended Euclidean algorithm: since gcd(Mᵢ, mᵢ) = 1 (guaranteed by the coprimality condition), Bézout's identity gives integers x, y such that Mᵢ·x + mᵢ·y = 1, and x mod mᵢ is the desired inverse.
Why does the solution have the form x + k·M?
The CRT guarantees a unique solution in the range [0, M). Any other solution must differ by a multiple of M, because the congruence conditions repeat with period M. So the complete solution set is {x, x+M, x+2M, x−M, …} = x + k·M for any integer k.
Where is CRT used in practice?
CRT has wide applications: RSA cryptography uses it to speed up decryption (Garner's formula); computer arithmetic uses it for multi-precision arithmetic without big-number overflow; competitive programming uses it to combine modular constraints; and calendar arithmetic uses it to find days satisfying multiple period conditions (e.g., 7-day week and 30-day cycle).
You Might Also Like
Explore 360+ Free Calculators
From math and science to finance and everyday life — all free, no account needed.