Chinese Remainder CalculatorFree online math calculator — instant results, no sign-up
Solve two congruences with coprime positive integer moduli.
About the Chinese Remainder Calculator
The Chinese Remainder Calculator solves two integer congruences with coprime positive integer moduli. It returns the least nonnegative integer satisfying both remainder conditions and the combined modulus that describes all solutions. With remainders 2 and 3 and moduli 3 and 5, it gives a least nonnegative solution of 8 and a combined modulus of 15.
- First remainder
- The integer remainder a in the first congruence x ≡ a (mod m), defaulting to 2, is dimensionless.
- First modulus
- The positive integer divisor m in the first congruence, defaulting to 3, is dimensionless and must be coprime to the second modulus.
- Second remainder
- The integer remainder b in the second congruence x ≡ b (mod n), defaulting to 3, is dimensionless.
- Second modulus
- The positive integer divisor n in the second congruence, defaulting to 5, is dimensionless and must be coprime to the first modulus.
Formula and method
Solve x ≡ a (mod m) and x ≡ b (mod n), with gcd(m,n) = 1. Choose Bézout coefficients u and v such that um + vn = 1. Then M = mn and x₀ = (avn + bum) mod M, where mod returns the least nonnegative residue. For a = 2, m = 3, b = 3, n = 5, choose u = 2 and v = −1 because 2·3 − 1·5 = 1. Thus M = 3·5 = 15 and x₀ = (2·(−1)·5 + 3·2·3) mod 15 = 8. All integer solutions are x = x₀ + kM.
- xAn integer satisfying both congruences.
- a, bThe first and second integer remainders, respectively.
- m, nThe first and second positive integer moduli, respectively.
- gcd(m,n)The greatest common divisor of the moduli; it must equal 1.
- u, vInteger Bézout coefficients satisfying um + vn = 1.
- MThe combined modulus mn.
- x₀The least nonnegative solution, satisfying 0 ≤ x₀ < M.
- kAny integer, used to generate every solution from x₀ + kM.
Check that both remainders are integers, both moduli are positive integers, and the moduli have greatest common divisor 1. The extended Euclidean algorithm supplies Bézout coefficients for the moduli. Combine the remainders using those coefficients, then reduce the result modulo the product of the moduli. Coprimality guarantees exactly one solution in the interval from 0 up to, but not including, that product.
Worked example
These are the calculator's starting values and the results it actually produces for them.
Inputs
- First remainder2
- First modulus3
- Second remainder3
- Second modulus5
Results
- Least nonnegative solution8
- Combined modulus15
How to use the Chinese Remainder Calculator
- 1Enter 2 in First remainder and 3 in First modulus to specify x ≡ 2 (mod 3).
- 2Enter 3 in Second remainder and 5 in Second modulus to specify x ≡ 3 (mod 5).
- 3Confirm that the moduli are positive integers and coprime: gcd(3,5) = 1.
- 4Run the calculation and read Least nonnegative solution = 8 and Combined modulus = 15.
- 5Verify that 8 leaves remainder 2 when divided by 3 and remainder 3 when divided by 5; express all solutions as x = 8 + 15k for integer k.
Reading your result
The Least nonnegative solution row gives the smallest integer at least zero that satisfies both congruences; for the default inputs, this is 8. The Combined modulus row gives the repetition interval for solutions; here it is 15. Together, the rows mean x ≡ 8 (mod 15), or equivalently x = 8 + 15k for any integer k. Both outputs are dimensionless.
Limitations
This tool is intended for exactly two congruences with integer remainders and coprime positive integer moduli. Zero, negative, or fractional moduli are outside its scope. Noncoprime moduli require a generalized Chinese remainder method and may yield either no solution or a solution modulo their least common multiple. Negative or oversized integer remainders are mathematically equivalent to their normalized residues. A modulus of 1 imposes no restriction; the Bézout formula also covers this case. Maximum supported input sizes depend on the calculator's integer arithmetic implementation.
Common questions
Why is the default solution 8 rather than either entered remainder?+
The solution must satisfy both remainder conditions simultaneously. Since 8 = 2·3 + 2 and 8 = 1·5 + 3, it has the required remainder for each modulus.
Why is the combined modulus 15?+
The moduli 3 and 5 are coprime, so their least common multiple is their product, 15. Adding or subtracting 15 preserves both remainder conditions.
Does this calculator return every solution?+
It summarizes every solution using two outputs rather than listing infinitely many integers. With the defaults, all solutions are exactly x = 8 + 15k, where k is any integer.
Can I use moduli that share a factor greater than 1?+
Not within this calculator's coprime-modulus scope. For noncoprime moduli, a solution exists only if gcd(m,n) divides b − a, and the combined modulus would be lcm(m,n), not necessarily mn.
Does the calculator save my information?+
Calculations run in your browser. While signed in, inputs and results are automatically recorded in account history; saving a result creates a separate saved record.
You might also like
Scientific Calculator
Full scientific calculator with trig, logs, powers, memory and degree/radian modes.
Fraction Calculator
Add, subtract, multiply and divide fractions.
Percentage Calculator
Percent of a number, what percent, and percent change.
Random Number Generator
Generate random integers in a range.
Percent Error Calculator
Error between an observed and true value.
Exponent Calculator
Raise a base to any power.
Results are estimates for informational purposes and are not financial, medical or legal advice.