Chinese Remainder Theorem Calculator
Solve systems of congruences using the Chinese Remainder Theorem. Find x such that x ≡ r1 (mod m1) and x ≡ r2 (mod m2).
About this calculator
This calculator solves a system of two modular congruences using the Chinese Remainder Theorem: given x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂), it finds the unique solution x modulo the combined modulus. When the two moduli are coprime (gcd = 1), the combined modulus is simply m₁ × m₂ and the engine solves directly via the extended Euclidean algorithm (extendedGcd). When they share a common factor, the engine switches to a generalized form: it first checks (remainder1 - remainder2) % g === 0 to confirm a solution exists at all, then works with the least common multiple (modulus1 / g) * modulus2 instead of the plain product — and reports "No solution exists" as text rather than a number when that check fails.
Remainder 2 has the largest measured effect on the Solution among the four inputs under a small nudge at the calculator's defaults, more than Remainder 1, Modulus 2, or Modulus 1. That ranking should not be read as a stable, monotonic relationship, though: because the solution is a residue modulo a combined value that itself depends on the inputs, increasing a remainder does not reliably increase the result — it can just as easily wrap around to a smaller residue, the way clock arithmetic does. Modulus 1's apparent lack of effect at the default values is a similar coincidence: at this particular starting point, two different valid moduli happen to produce the same numeric solution, not proof the modulus never matters.
Inputs
Results
Solution (x)
8
How to Use This Calculator
- Enter Remainder 1 (r₁), Modulus 1 (m₁), and Remainder 2 (r₂).
- Set Modulus 2 (m₂).
- Review the Solution (x) result.
- Use Combined Modulus and Verification to inform your decision.
- Use the chart to visualize the results and explore different scenarios by adjusting inputs.
How the result changes with Remainder 2 (r₂)
| Remainder 2 (r₂) | Solution (x) |
|---|---|
| 1.5 | 11 |
| 2.25 | 2 |
| 4.5 | 14 |
| 7.5 | 2 |
What each input means
- Remainder 1 (r₁)
- First remainder: x ≡ r₁ (mod m₁)
- Modulus 1 (m₁)
- First modulus
- Remainder 2 (r₂)
- Second remainder: x ≡ r₂ (mod m₂)
- Modulus 2 (m₂)
- Second modulus
How this is calculated
Worked example, using the default values
- Identify Input Parameters4 parametersRemainder 1 (r₁) = 2, Modulus 1 (m₁) = 3, Remainder 2 (r₂) = 3, Modulus 2 (m₂) = 5 = 4 input(s) provided
- Calculate Solution8 = 8
- Calculate Combined Modulus15 = 15
- Calculate VerificationVerification8 mod 3 = 2, 8 mod 5 = 3 = 8 mod 3 = 2, 8 mod 5 = 3
Engine last updated . Checked against 3 independently-derived tests — how we verify calculators. Built by Paul Gunder, a software engineer, not a licensed financial, medical, or legal professional.
Frequently Asked Questions
What does 'No solution exists' mean, and when does the calculator return it?
It appears when the two moduli share a common factor greater than 1 and the two remainders are incompatible with that shared factor — checked directly in the code as (remainder1 - remainder2) % g === 0, where g is the GCD of the moduli. If that check fails, no whole number can satisfy both congruences simultaneously, so the engine reports the text result instead of a number.
Why does Remainder 2 move the Solution more than Remainder 1 does at the default values?
Under a small nudge to each input in turn, Remainder 2 produces a larger swing in the computed Solution than Remainder 1, Modulus 1, or Modulus 2 do at the calculator's default 2/3/3/5 setup. That is a measured ranking at this specific starting point, not a general rule — modular solutions depend on all four inputs together, and which one moves the result most can change entirely at a different starting point.
Does increasing a remainder always increase the Solution?
No. The Solution is a residue taken modulo the combined value with ((solution % modulus) + modulus) % modulus, so it always lands back inside a bounded range no matter how the inputs change. Raising a remainder can just as easily wrap the result around to a smaller number as it can raise it, the same way adding hours to a clock can roll it back past midnight.
What happens if Modulus 1 and Modulus 2 aren't coprime?
The engine detects this via gcd(modulus1, modulus2) and switches from the simple Chinese Remainder Theorem formula to a generalized version that works with the least common multiple of the two moduli instead of their plain product, and uses extendedGcd(modulus1 / g, modulus2 / g) to find a solution consistent with the shared factor, when one exists.
Related Calculators
The questions that sit next to this one — chosen by subject, including calculators filed under a different category.
Modular Arithmetic Calculator
Perform modular addition, multiplication, and exponentiation. Calculate (a op b) mod m with equivalence classes.
Number TheoryEuler's Totient Calculator
Calculate Euler's totient function phi(n) — the count of integers from 1 to n that are coprime to n.
Estate PlanningCharitable Remainder Trust Calculator
Calculate CRT income stream, charitable deduction, and tax savings.
Number TheoryDivisibility Calculator
Check if one number divides another. Shows remainder, quotient, and total factor pair count.
More in Math & Statistics.