Chinese Remainder Theorem Calculator
Finds the smallest non-negative integer x satisfying a system of two or three simultaneous modular congruences. Used in cryptography, scheduling problems, and number theory proofs.
About this calculator
The Chinese Remainder Theorem (CRT) states that if m₁, m₂, … are pairwise coprime moduli, the system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), … has a unique solution modulo M = m₁ × m₂ × …. The construction computes Mᵢ = M / mᵢ and finds yᵢ such that Mᵢ × yᵢ ≡ 1 (mod mᵢ) (the modular inverse). The solution is x = (Σ aᵢ × Mᵢ × yᵢ) mod M. For two congruences x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂), this gives x = (a₁ × M₂ × y₁ + a₂ × M₁ × y₂) mod M. The result is the unique least non-negative solution in [0, M).
How to use
Solve: x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Here M = 3 × 5 = 15, M₁ = 5, M₂ = 3. Find y₁: 5 × y₁ ≡ 1 (mod 3) → y₁ = 2. Find y₂: 3 × y₂ ≡ 1 (mod 5) → y₂ = 2. Compute x = (2 × 5 × 2 + 3 × 3 × 2) mod 15 = (20 + 18) mod 15 = 38 mod 15 = 8. Verify: 8 mod 3 = 2 ✓ and 8 mod 5 = 3 ✓.
Frequently asked questions
What are the requirements for the Chinese Remainder Theorem to apply?
The CRT requires that all moduli be pairwise coprime, meaning any two moduli share no common factor other than 1. For example, moduli 3, 5, and 7 are pairwise coprime. If moduli share a factor (e.g., 4 and 6), the system may have no solution or infinitely many, and the standard CRT construction does not directly apply. Always verify coprimality before using this calculator.
How does the Chinese Remainder Theorem work in cryptography?
CRT is widely used to speed up RSA decryption. Instead of computing m = c^d mod n directly, decryption is split into two smaller exponentiations modulo p and q (the prime factors of n), then recombined via CRT. This approach is roughly four times faster than direct computation. CRT also underpins secret sharing schemes and several primality-proving algorithms.
Why does the Chinese Remainder Theorem give a unique solution modulo M?
Because the moduli are coprime, the map x ↦ (x mod m₁, x mod m₂, …) is a ring isomorphism between ℤ/Mℤ and ℤ/m₁ℤ × ℤ/m₂ℤ × …. This bijectivity guarantees exactly one solution in [0, M). Any other solution differs by a multiple of M, so while there are infinitely many integer solutions, they all fall in the same residue class modulo M.