Chinese Remainder Theorem Calculator
Enter up to 6 congruences and instantly find the unique solution x via the Chinese Remainder Theorem.
Use the Chinese Remainder Theorem Calculator
System of Congruences
Enter x ≡ r (mod m) for each row. All moduli must be pairwise coprime.
Examples
Enter congruences on the left and press Solve.
Unique Solution
Step-by-step derivation
Step 1 — Compute M (product of all moduli)
Step 2 — Partial products Mi = M / mi
| i | mi | ri | Mi = M/mi |
|---|
Step 3 — Modular inverses yi ≡ Mi⁻¹ (mod mi)
| i | Mi | mi | yi = Mi⁻¹ mod mi | ri × Mi × yi |
|---|
Step 4 — Sum and reduce mod M
Summary
The Chinese Remainder Theorem (CRT) states that if the moduli m1, m2, …, mk are pairwise coprime, there is a unique solution x modulo M = m1 × m2 × … × mk satisfying all congruences simultaneously. This tool lets you enter up to 6 congruences, verifies the coprimality conditions, and displays the smallest non-negative solution together with the full derivation.
How it works
- Enter at least 2 rows of remainder r and modulus m (e.g. r=2, m=3 means x ≡ 2 mod 3).
- Click "Solve" — the tool checks that all moduli are pairwise coprime.
- For each congruence the tool computes the partial product Mi = M / mi and its modular inverse.
- The solution is x = Σ ri × Mi × Mi⁻¹ (mod M), reduced to the range [0, M).
- All intermediate values are shown so you can follow every step.
Use cases
- Solving number theory homework and competition problems.
- Cryptography: combining partial results from smaller moduli (RSA-CRT optimisation).
- Calendar and scheduling puzzles that reduce to simultaneous remainders.
- Checking understanding of the CRT proof by inspecting each intermediate step.
- Computer science: fast multi-precision arithmetic via the CRT representation.
- Puzzle solving: "What is the smallest number that leaves remainder a when divided by b?"