Chinese Remainder Theorem Calculator
Solve a system of congruences x ≡ aᵢ (mod mᵢ) with the Chinese remainder theorem: the smallest solution, the general solution, step-by-step merging, and non-coprime moduli.
How it works
x ≡ aᵢ (mod mᵢ) · coprime moduli: x = Σ aᵢ·Mᵢ·yᵢ mod M, M = Πmᵢ, Mᵢ = M/mᵢ, yᵢ = Mᵢ⁻¹ mod mᵢ · general case: merge pairs, solvable iff aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)), modulus = lcm
The Chinese remainder theorem says that if the moduli are pairwise coprime, a system of congruences has exactly one solution modulo the product of the moduli. This calculator merges the congruences two at a time with the extended Euclidean algorithm, which also handles moduli that share factors: then a solution exists only if the remainders agree modulo the common factor, and it is unique modulo the least common multiple.
Worked example
Sunzi’s classic puzzle: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). Merging the first two gives x ≡ 8 (mod 15); adding the third gives x ≡ 23 (mod 105). So the smallest solution is 23 and every solution is x = 23 + 105k.
Sources: Chinese remainder theorem — Wikipedia · Chinese Remainder Theorem — Wolfram MathWorld
Frequently asked questions
Do the moduli have to be coprime?
No. With coprime moduli there is always a solution. If two moduli share a factor g, a solution exists only when their remainders are congruent modulo g, and the answer is unique modulo the lcm.
How do you solve the Chinese remainder theorem by hand?
Compute M = m₁m₂…, Mᵢ = M/mᵢ and the inverse yᵢ of Mᵢ modulo mᵢ; then x = Σ aᵢMᵢyᵢ mod M. For 2, 3, 2 mod 3, 5, 7: 2·35·2 + 3·21·1 + 2·15·1 = 233 ≡ 23 (mod 105).
What is the Chinese remainder theorem used for?
Calendar and cycle problems, speeding up RSA decryption, secret sharing, and arithmetic with very large numbers split into smaller residues.
Can remainders be negative or larger than the modulus?
Yes. They are reduced first: x ≡ −1 (mod 5) is the same as x ≡ 4 (mod 5).
Related calculators
This calculator is for educational purposes. Double-check important results before acting on them.