Calculators
Chinese Remainder Theorem Calculator
Solve two modular congruences with exact integer arithmetic, including non-coprime moduli, solution periods and verification.
Solve x ≡ a (mod m) and x ≡ b (mod n). Enter signed remainders and positive moduli, each up to 100 digits. Calculations stay in your browser.
How the generalized Chinese remainder theorem works
For x ≡ a (mod m) and x ≡ b (mod n), a common integer solution exists exactly when gcd(m, n) divides b − a. The extended Euclidean algorithm supplies the coefficient needed to combine the congruences. When compatible, all solutions differ by lcm(m, n). For x ≡ 2 (mod 3) and x ≡ 3 (mod 5), the smallest non-negative solution is 8 and all solutions are 8 + 15t. Non-coprime example: x ≡ 2 (mod 4) and x ≡ 6 (mod 8) gives 6 + 8t. Negative remainders are normalized. Modulus 1 imposes no restriction. Enter up to 100 digits per input; decimals, plus signs, separators and scientific notation are rejected. Exact BigInt arithmetic runs locally without uploading or storing inputs.
Frequently Asked Questions
Everything you need to know about this tool, how it works, and privacy.
Do the moduli have to be coprime?
No. A solution exists if the remainder difference is divisible by the GCD of the moduli. Coprime moduli always satisfy this condition.
What does the solution period mean?
The period is the least common multiple of the two moduli. Adding or subtracting any whole multiple of it gives another solution.
Can I use negative remainders or modulus 1?
Yes. Negative remainders are normalized to non-negative residues. Modulus 1 imposes no restriction. Zero and negative moduli are rejected.
Are large answers exact and private?
Yes. Browser BigInt arithmetic preserves every integer digit for inputs up to 100 digits each. Inputs are not uploaded or stored.