Chinese Remainder Theorem Solver
Find the unique integer that satisfies multiple simultaneous modular congruences. Use this when solving scheduling puzzles, cryptographic problems, or any system where a number must leave specific remainders under different divisors.
About this calculator
The Chinese Remainder Theorem (CRT) states that if m₁, m₂, … are pairwise coprime moduli, there exists a unique solution x modulo M = m₁ × m₂ × … satisfying x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂), etc. The construction computes Mᵢ = M / mᵢ for each congruence, then finds the modular inverse yᵢ such that Mᵢ × yᵢ ≡ 1 (mod mᵢ) using the Extended Euclidean Algorithm. The solution is x = (r₁M₁y₁ + r₂M₂y₂ + r₃M₃y₃) mod M. Modular inverses exist only when gcd(Mᵢ, mᵢ) = 1, which is guaranteed when all moduli are pairwise coprime. The result is the smallest non-negative integer satisfying all congruences simultaneously.
How to use
Suppose you want x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Enter r₁=2, m₁=3, r₂=3, m₂=5, r₃=2, m₃=7. M = 3×5×7 = 105. M₁=35, M₂=21, M₃=15. Modular inverses: y₁=2 (35×2 mod 3=1), y₂=1 (21×1 mod 5=1), y₃=1 (15×1 mod 7=1). x = (2×35×2 + 3×21×1 + 2×15×1) mod 105 = (140+63+30) mod 105 = 233 mod 105 = 23. The answer is x = 23.
Frequently asked questions
What does it mean for moduli to be pairwise coprime in the Chinese Remainder Theorem?
Pairwise coprime means every pair of moduli shares no common factor other than 1, i.e., gcd(mᵢ, mⱼ) = 1 for all i ≠ j. This condition is essential because it guarantees that the modular inverses yᵢ exist. If two moduli share a factor, the system may have no solution or infinitely many, and the standard CRT formula breaks down. For example, moduli 3, 5, and 7 are pairwise coprime, while 4 and 6 are not (they share factor 2).
How is the Chinese Remainder Theorem used in real-world cryptography?
CRT is central to RSA encryption, where it dramatically speeds up private-key decryption by breaking one large modular exponentiation into two smaller ones modulo the prime factors p and q. It also underpins secret sharing schemes, where a secret is split across multiple modular residues. In computer arithmetic, CRT enables multi-precision arithmetic by representing large integers as tuples of smaller residues, performing operations in parallel, then reconstructing the result.
Why does the Chinese Remainder Theorem always produce a unique solution within the range 0 to M−1?
When all moduli are pairwise coprime, the map from integers mod M to tuples of residues (mod m₁, mod m₂, …) is a bijection by the CRT. Because M = m₁ × m₂ × … equals the total number of residue combinations, every tuple maps to exactly one value in [0, M−1]. This uniqueness means no two distinct integers below M can satisfy all the congruences simultaneously, making the solution well-defined and canonical.