Chinese Remainder Theorem Calculator
Solve systems of congruences of the form x ≡ a (mod m). This tool supports pairwise coprime and non-coprime moduli, and reports when no solution exists.
What this CRT calculator does
This CRT calculator finds a number x that satisfies multiple modular equations at once. For example, you might need a value that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. Instead of trial-and-error, the calculator uses a reliable number-theory method to combine constraints into a single answer.
The output is given in canonical form: x ≡ r (mod M). That means every solution is x = r + kM for any integer k.
Quick refresher: what is CRT?
The core idea
The Chinese Remainder Theorem says that a system of congruences can often be merged into one equivalent congruence. When moduli are pairwise coprime, a unique solution exists modulo the product of all moduli.
What if moduli are not coprime?
A solution can still exist. For two equations x ≡ a (mod m) and x ≡ b (mod n), consistency requires: a ≡ b (mod gcd(m, n)). If this condition fails at any merge step, there is no solution.
How to use the calculator
- Enter each congruence as a remainder and modulus.
- Use positive moduli (1, 2, 3, ...).
- Click + Add Congruence for more equations.
- Click Calculate CRT Solution.
- Read the final form x ≡ r (mod M) and optional merge steps.
Worked examples
Example 1: Pairwise coprime moduli
For: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7), the calculator returns: x ≡ 23 (mod 105). So solutions are 23, 128, 233, and so on.
Example 2: Non-coprime but consistent
For: x ≡ 2 (mod 6), x ≡ 8 (mod 9), a solution exists because 2 and 8 are congruent modulo gcd(6,9)=3. One compact result is: x ≡ 8 (mod 18).
Example 3: Inconsistent system
For: x ≡ 1 (mod 4), x ≡ 2 (mod 6), no solution exists because differences violate the gcd consistency rule. The calculator reports this directly.
How the algorithm works behind the scenes
The calculator merges congruences one at a time. At each step it solves: x ≡ a (mod m) and x ≡ b (mod n). It uses the extended Euclidean algorithm to compute modular inverses efficiently and safely.
- Normalize each remainder to the range 0..m−1.
- Compute g = gcd(m, n).
- If (b − a) is not divisible by g, stop: no solution.
- Otherwise merge into one congruence modulo lcm(m, n).
Practical applications of CRT
- Cryptography and RSA-related optimizations
- Scheduling problems with repeating cycles
- Hashing and residue number systems
- Puzzle-solving and competitive programming
- Clock arithmetic and synchronization tasks
Common mistakes to avoid
- Using modulus 0 (invalid in modular arithmetic)
- Entering decimal values instead of integers
- Assuming non-coprime moduli always fail
- Forgetting that solutions are periodic, not single-value only
FAQ
Does this support very large integers?
Yes. This page uses JavaScript BigInt, so it can handle integers larger than typical 32-bit or 64-bit ranges.
Why is my answer different from another website?
Results may be equivalent but expressed differently. If two answers are congruent modulo the same modulus, they represent the same solution set.
Can I use negative remainders?
Yes. The calculator normalizes them automatically into standard non-negative form modulo m.