How this calculator works
Combine congruences one at a time. A shared factor is allowed only when the corresponding remainders agree modulo that factor. The extended Euclidean algorithm finds the needed inverse after removing that factor. The combined modulus is the least common multiple, and exact integer arithmetic preserves large periods.
Formula
To combine x = r (mod M) with x = a (mod m), let g = gcd(M,m). Require g | (a-r), solve (M/g)k = (a-r)/g (mod m/g), then use x = r + Mk with period lcm(M,m).
Worked example
x = 2 (mod 3), x = 3 (mod 5) gives x = 8 + 15k. Adding x = 2 (mod 7) gives x = 23 + 105k.
Advertisement
Frequently asked questions
Must the moduli be coprime?
No. For example, x = 2 mod 4 and x = 4 mod 6 have solution 10 mod 12. Conflicting remainders are rejected.
Are negative remainders allowed?
Yes. Each is interpreted modulo its positive modulus.
What does k mean?
Any integer. Adding or subtracting the period produces another solution to every congruence.