Chinese Remainder Theorem Calculator

How to Use This Calculator

1. Enter remainders a₁, a₂ and moduli m₁, m₂. The unique solution x mod M appears instantly.
2. Use 3 Congruences tab for three simultaneous equations.
3. Use Coprimality Check to verify moduli are pairwise coprime before solving.
4. Use Professional to see the explicit formula with Bézout coefficients.

Formula

Example

Frequently Asked Questions

• What is the Chinese Remainder Theorem? ▼
  The Chinese Remainder Theorem (CRT) states that if moduli m₁, m₂, …, mₖ are pairwise coprime (every pair shares no common factor), then for any choice of remainders a₁, a₂, …, aₖ there exists a unique solution x modulo M = m₁ × m₂ × … × mₖ satisfying all congruences simultaneously: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), etc. The solution is unique within [0, M). This theorem transforms a system of congruences into a single congruence, which is powerful for large-number arithmetic.
• What does "pairwise coprime" mean? ▼
  "Pairwise coprime" means every pair of moduli shares no common factor other than 1: gcd(mᵢ, mⱼ) = 1 for all pairs i ≠ j. Example of pairwise coprime moduli: 3, 5, 7 — each pair (3,5), (3,7), (5,7) has GCD = 1. Non-example: 4, 6, 15 — gcd(4,6) = 2 ≠ 1, so they are not pairwise coprime. The pairwise coprime condition is required by the basic CRT. If moduli are not coprime, a generalized CRT handles some cases, but the system may have no solution or infinitely many.
• How do I solve x ≡ 2 (mod 3), x ≡ 3 (mod 5)? ▼
  Step 1: M = 3 × 5 = 15. Step 2: M₁ = M/m₁ = 5, M₂ = M/m₂ = 3. Step 3: find y₁ = M₁⁻¹ mod m₁ = 5⁻¹ mod 3 = 2 (since 5×2=10≡1 mod 3). Find y₂ = M₂⁻¹ mod m₂ = 3⁻¹ mod 5 = 2 (since 3×2=6≡1 mod 5). Step 4: x = a₁M₁y₁ + a₂M₂y₂ = 2×5×2 + 3×3×2 = 20 + 18 = 38 ≡ 38 mod 15 = 8. Verify: 8 mod 3 = 2 ✓, 8 mod 5 = 3 ✓. The unique solution is x = 8 (mod 15).
• What if moduli are not coprime? ▼
  If two moduli share a common factor, the basic CRT does not apply. The system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) with gcd(m₁,m₂) = d may have no solution (if d does not divide a₁ − a₂) or infinitely many solutions modulo lcm(m₁,m₂) (if d divides a₁ − a₂). For example, x ≡ 1 (mod 4) and x ≡ 3 (mod 6): gcd=2, a₁−a₂=−2, which 2 divides, so solutions exist: x ≡ 9 (mod 12). This calculator checks coprimality automatically and reports when the basic CRT cannot proceed.
• What are real-world uses of CRT? ▼
  CRT has several important applications: RSA-CRT decryption decomposes a large modular exponentiation into two smaller ones (mod p and mod q), speeding up RSA by about 4×. Calendar cycles: "what day of the week falls on a given date?" uses modular arithmetic with moduli 7, 30, 365. Error-correcting codes in communications use CRT for efficient recovery from errors. Computer arithmetic: representing large integers using several small moduli (Residue Number System) enables fast parallel computation. Secret sharing (Mignotte threshold schemes) uses CRT to split secrets.

Related Calculators