Chinese remainder theorem calculator
Type your congruences separated by semicolons, for example x ≡ 2 (mod 3); x ≡ 3 (mod 5). The calculator merges them one by one, tells you if the system is solvable and gives the solution as x ≡ r (mod M).
Runs in your browser: nothing you enter is sent anywhere.
How to use it
- Type the congruences, one per
;. The leading x ≡ and the word mod are optional: 2 mod 3; 3 mod 5 works as well.
- Read the solution x ≡ r (mod M). If the system cannot be solved, the steps show which pair of congruences clashes.
How it works
The first two congruences are merged into one, that result is merged with the third, and so on. Every merge uses the extended Euclidean algorithm on the two moduli, so solutions and moduli can have dozens of digits: all arithmetic uses big integers.
Worked example
x ≡ 2 (mod 4) and x ≡ 4 (mod 6) have moduli with gcd 2. Since 2 divides 4 − 2 = 2, a solution exists, and the combined modulus is lcm(4, 6) = 12. The solution is x ≡ 10 (mod 12): 10 = 2·4 + 2 and 10 = 1·6 + 4.
By contrast x ≡ 1 (mod 4), x ≡ 2 (mod 6) has no solution: gcd = 2 does not divide 2 − 1 = 1.
Tips
- With non-coprime moduli the congruences must agree on their shared part: a number that is 1 mod 4 is odd, so it cannot also be 2 mod 6, which is even.
- Related tools: GCD and LCM calculator, modulo calculator.
Frequently asked questions
What does the Chinese remainder theorem say?
If the moduli m₁, m₂, … are pairwise coprime, the system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), … always has a solution, and it is unique modulo the product m₁m₂…. The classic example x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) gives x ≡ 23 (mod 105).
What if the moduli are not coprime?
Two congruences x ≡ a (mod m) and x ≡ b (mod n) are compatible exactly when gcd(m, n) divides b − a. If so, they merge into one congruence modulo lcm(m, n); if not, the system has no solution. This calculator checks that at every step.
How are two congruences merged?
With g = gcd(m, n), write x = a + m·t. Then t must satisfy (m/g)·t ≡ (b − a)/g (mod n/g), which is solved with the modular inverse of m/g from the extended Euclidean algorithm.
How are negative remainders handled?
A remainder is reduced into the range 0…m−1 first, so −1 mod 5 is the same as 4 mod 5.
What are all the solutions?
If x₀ is the smallest non-negative solution and M the combined modulus, every solution is x₀ + M·k for any whole number k, positive or negative.