Compatibility
a ≡ b (mod gcd(m, n))
The pair x ≡ a (mod m) and x ≡ b (mod n) has a solution exactly when the remainders agree modulo the GCD.
Chinese Remainder Theorem Calculator with Steps
Enter the congruences
For each row, enter x ≡ remainder (mod modulus).
Private by design: your congruences are validated and solved on this device. They are not uploaded, stored, or added to the page URL.
Advertisement
How the Chinese Remainder Theorem works
Merge multiplier
t ≡ ((b − a)/g)·(m/g)⁻¹ (mod n/g)
After dividing by g = gcd(m,n), the reduced moduli are coprime, so the required inverse exists.
Combined congruence
x ≡ a + mt (mod lcm(m, n))
The merged result replaces the first two congruences. Repeating this step incorporates every row.
If all moduli are pairwise coprime, the classic theorem guarantees one residue class modulo their product. The generalized theorem used here also permits shared factors; when the system is compatible, the final period is the least common multiple of all moduli.
Chinese Remainder Theorem examples
Pairwise-coprime moduli
For x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7), the smallest nonnegative solution is x = 23. Every solution is x = 23 + 105k for an integer k.
Compatible moduli with a shared factor
The system x ≡ 2 (mod 6) and x ≡ 8 (mod 14) is compatible because both remainders are 0 modulo gcd(6,14)=2. Its answer is x ≡ 8 (mod 42).
An incompatible system
The congruences x ≡ 1 (mod 4) and x ≡ 2 (mod 6) cannot both hold. Their remainder difference is 1, which is not divisible by gcd(4,6)=2.
Input rules, assumptions, and limits
Enter base-10 integers without commas, decimal points, scientific notation, or expressions. Remainders may be negative or larger than their moduli; each is normalized to the interval from 0 through m − 1. Every modulus must be a positive integer of at least 2.
The calculator combines congruences from top to bottom with the generalized CRT. It reports the smallest nonnegative solution x₀ and the complete family x = x₀ + kL, where L is the least common multiple of the moduli and k is any integer. A no-solution result is definitive for the entered system.
A system may contain 2 to 12 congruences, and each input is limited to 100 digits excluding an optional sign. JavaScript BigInt keeps all displayed integer arithmetic exact. These limits keep validation and step output responsive on typical mobile devices.
Calculation note: the merge formula, compatibility condition, canonical normalization, and examples were checked against their defining congruences. Last reviewed: .
Chinese Remainder Theorem calculator FAQ
What does the Chinese Remainder Theorem calculate?
It finds an integer that satisfies several remainder conditions at once. For pairwise-coprime moduli, the solution is unique modulo their product.
Do the moduli have to be coprime?
No. This calculator uses the generalized CRT. Moduli may share factors, provided the affected remainders agree modulo the GCD of their moduli.
When does a system have no solution?
A pair x ≡ a (mod m) and x ≡ b (mod n) is incompatible when b − a is not divisible by gcd(m,n). One incompatible merge makes the complete system unsolvable.
Why are there infinitely many solutions?
If x₀ is one solution, then x₀ + kL is also a solution for every integer k, where L is the least common multiple of all moduli.
Can a remainder be negative or greater than the modulus?
Yes. The tool converts it to the equivalent canonical remainder from 0 through m − 1 before combining the congruences.
What happens when a modulus is repeated?
Repeated moduli are valid if their canonical remainders match. Different remainders for the same modulus describe an incompatible system.
What is the difference between CRT and a modular inverse?
A modular inverse solves one multiplication congruence. The CRT combines several remainder congruences; modular inverses appear inside the combining calculation.
Does the calculator store my inputs?
No. Validation, solving, copy preparation, and text-file creation all run locally in your browser. The tool does not transmit or save the entered congruences.