Chinese Remainder Theorem Solver
Solve systems of simultaneous modular congruences using the Chinese Remainder Theorem (CRT). Essential for cryptography, competitive programming, and advanced number-theory coursework.
About this calculator
The Chinese Remainder Theorem states that if the moduli m₁, m₂, …, mₖ are pairwise coprime, there exists a unique solution x modulo M = m₁ × m₂ × … × mₖ satisfying x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), etc. The construction formula is x = Σ aᵢ · Mᵢ · yᵢ (mod M), where Mᵢ = M / mᵢ and yᵢ is the modular inverse of Mᵢ with respect to mᵢ (i.e., Mᵢ · yᵢ ≡ 1 mod mᵢ). This calculator uses Fermat's little theorem to approximate yᵢ = Mᵢ^(mᵢ−2) mod mᵢ, which is exact when mᵢ is prime. The result is the smallest non-negative integer satisfying all congruences simultaneously.
How to use
Suppose you need x ≡ 2 (mod 3), x ≡ 3 (mod 5). Enter remainder1 = 2, modulus1 = 3, remainder2 = 3, modulus2 = 5. M = 3 × 5 = 15. M₁ = 5, M₂ = 3. Find y₁: 5^(3−2) mod 3 = 5 mod 3 = 2. Find y₂: 3^(5−2) mod 5 = 27 mod 5 = 2. x = (2×5×2 + 3×3×2) mod 15 = (20 + 18) mod 15 = 38 mod 15 = 8. Answer: x = 8.
Frequently asked questions
What conditions must be met for the Chinese Remainder Theorem to guarantee a unique solution?
The theorem guarantees a unique solution modulo M = m₁ × m₂ × … × mₖ only when all moduli are pairwise coprime — meaning every pair shares no common factor other than 1. For example, moduli 3, 5, and 7 are pairwise coprime, but 4 and 6 are not (both share factor 2). When moduli are not coprime, a solution may still exist but is not guaranteed, and the uniqueness property breaks down. Always verify coprimality before applying CRT.
How is the Chinese Remainder Theorem used in cryptography?
CRT is a cornerstone of RSA cryptography, where it speeds up private-key decryption significantly. Instead of performing one large modular exponentiation mod n, the computation is split into two smaller ones mod p and mod q (the prime factors of n), then recombined via CRT. This can reduce decryption time by a factor of four. CRT is also used in secret-sharing schemes and in constructing hash functions with desired period properties.
Why does this calculator use Fermat's little theorem to find modular inverses?
Fermat's little theorem states that for a prime p and integer a not divisible by p, a^(p−1) ≡ 1 (mod p), so a^(p−2) ≡ a⁻¹ (mod p). This gives a direct formula for the modular inverse without running the extended Euclidean algorithm. The calculator uses yᵢ = Mᵢ^(mᵢ−2) mod mᵢ for this reason. Note this approach is exact only when mᵢ is prime; for composite moduli the extended Euclidean algorithm is more appropriate.