Math
Chinese Remainder Theorem Calculator
Type one congruence per line, such as x ≡ 2 (mod 3), and the calculator finds every integer that satisfies all of them at once.
It verifies the moduli are pairwise coprime, computes N = n₁n₂…, each N_i = N / n_i, the inverse of N_i modulo n_i by the extended Euclidean algorithm, and the sum Σ a_i N_i y_i, then reduces it to the smallest solution and writes the general solution x = x₀ + Nk. When moduli share factors it checks consistency and solves by merging pairs, or explains exactly why no solution exists.
Each line can be written as x ≡ 2 (mod 3), 2 mod 3, or simply 2, 3 (remainder first, then modulus). Up to 12 lines.
Try an example
Result
Smallest solution x
—
- Solution
- —
- General solution
- —
- Combined modulus N
- —
- Check
- —
Student quick launch
Grade planning, algebra checks, and formulas students reach for most.
Study path
Use this calculator with
Follow these when you want the formula behind the answer, a short lesson, or nearby tools in the same topic.
What the Chinese remainder theorem calculator solves
The Chinese remainder theorem says that if the moduli n₁, n₂, …, n_k are pairwise coprime, then for any residues a₁, …, a_k there is exactly one x between 0 and N - 1 (N = n₁n₂…n_k) with x ≡ a_i (mod n_i) for every i, and every solution differs from it by a multiple of N. The classic example: a number leaves remainder 2 when divided by 3, 3 when divided by 5, and 2 when divided by 7; the answer is 23, and then 128, 233, … every 105.
The constructive method, step by step
- Check the moduli are pairwise coprime and compute N = 3 × 5 × 7 = 105.
- For each congruence compute N_i = N / n_i: N₁ = 35, N₂ = 21, N₃ = 15.
- Find y_i, the inverse of N_i The remainder left over after dividing one whole number by another. n_i: 35 ≡ 2 (mod 3) so y₁ = 2; 21 ≡ 1 (mod 5) so y₂ = 1; 15 ≡ 1 (mod 7) so y₃ = 1.
- Add the terms a_i × N_i × y_i: 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 140 + 63 + 30 = 233.
- Reduce: 233 mod 105 = 23. Check: 23 = 7 × 3 + 2, 4 × 5 + 3, 3 × 7 + 2.
| i | a_i | n_i | N_i | y_i | a_i N_i y_i |
|---|---|---|---|---|---|
| 1 | 2 | 3 | 35 | 2 | 140 |
| 2 | 3 | 5 | 21 | 1 | 63 |
| 3 | 2 | 7 | 15 | 1 | 30 |
Why it works: each term a_i N_i y_i is a multiple of every modulus except n_i, and modulo n_i it equals a_i × 1. So the sum matches every congruence at once. The calculator's table reproduces exactly these columns for your system.
When the moduli are not coprime
If two moduli share a factor g, the system is solvable only when the corresponding residues agree modulo g: x ≡ 1 (mod 4) and x ≡ 3 (mod 6) works (9 satisfies both), but x ≡ 1 (mod 4) and x ≡ 2 (mod 6) cannot both hold because one makes x odd and the other even. When consistent, the solution is unique modulo the lcm of the moduli rather than the product. The calculator detects this case, merges the congruences pairwise, and reports the lcm.
How to use it
- Enter each congruence on its own line as x ≡ a (mod n), a mod n, or a, n.
- Read the smallest non-negative solution and the modulus it repeats with.
- Use the table to copy the N_i, inverse, and term columns into your work.
- Open Show the work for the coprime check, each inverse computation, and the final reduction.
How to read the answer
The smallest solution is the unique answer between 0 and N - 1. The general solution x₀ + Nk lists every integer that works, positive or negative. The check line confirms each remainder. If the moduli were not pairwise coprime the panel says so and N is the lcm instead of the product; if the system is inconsistent, the error explains which pair conflicts and why.
Common mistakes and edge cases
- Applying the product formula to moduli that share a factor, such as 4 and 6; check pairwise coprimality first.
- Using N_i mod n_i instead of its inverse; y_i must satisfy N_i × y_i ≡ 1 (mod n_i).
- Forgetting to reduce the final sum mod N; 233 is a solution but 23 is the smallest one.
- Writing the modulus before the remainder when entering 2, 3 (it means remainder 2, modulus 3).
- Declaring 'no solution' for non-coprime moduli without testing consistency; x ≡ 1 (mod 4), x ≡ 3 (mod 6) does have solutions (x ≡ 9 mod 12).
Worked examples
Sun Tzu's problem
Remainders 2, 3, 2 modulo 3, 5, 7 → 23.
Smallest solution x
23
Two congruences
x ≡ 3 (mod 4), x ≡ 5 (mod 9) → 23.
Smallest solution x
23
Short comma form
Same as above using 'remainder, modulus'.
Smallest solution x
23
Zero residues
x ≡ 0 (mod 6), x ≡ 0 (mod 35) → 0 (mod 210).
Smallest solution x
0
Negative residue
x ≡ -1 (mod 5), x ≡ 2 (mod 7) → 9.
Smallest solution x
9
Non-coprime but consistent
x ≡ 1 (mod 4), x ≡ 3 (mod 6) → 9 (mod 12).
Smallest solution x
9
Large moduli
Primes near 10^6.
Smallest solution x
482,322,570,419
Inconsistent system
x ≡ 1 (mod 4) and x ≡ 2 (mod 6) clash on parity.
Smallest solution x
Error
Unreadable line
Bad syntax is rejected.
Smallest solution x
Error
Frequently asked questions
What does the Chinese remainder theorem say?+
If the moduli are pairwise coprime, a system x ≡ a_i (mod n_i) has exactly one solution modulo the product N of the moduli. Every solution is that number plus a multiple of N.
How do I solve a system of congruences by hand?+
Compute N, then for each congruence N_i = N/n_i and the inverse y_i of N_i mod n_i. Add a_i × N_i × y_i over all i and reduce mod N. The table on this page follows exactly that recipe.
What if the moduli are not coprime?+
A solution exists only when the residues agree modulo every shared factor; then it is unique modulo the lcm of the moduli. The calculator checks this and solves by merging congruences two at a time.
Why is the answer given modulo N?+
Because adding N changes nothing in any congruence: N is a multiple of every modulus. So 23, 128, 233, … all solve Sun Tzu's problem.
What is the classic Chinese remainder theorem example?+
Sun Tzu's puzzle from the 3rd century: a number has remainder 2 mod 3, 3 mod 5, and 2 mod 7. The smallest answer is 23.
Where is the Chinese remainder theorem used?+
Fast RSA decryption, big-integer multiplication, secret sharing, and any situation where several cycles must line up, such as calendars or gear trains.
Can the residues be negative or larger than the modulus?+
Yes. They are reduced first: x ≡ -1 (mod 5) is the same as x ≡ 4 (mod 5).
About this calculator
- Written by
- mathcheck editorial team
- Last reviewed
- September 4, 2026
Method
- Uses the values entered by the user and stable formulas documented on the page.
References
- NIST Dictionary of Algorithms and Data Structures, Chinese remainder theorem
- Knuth, The Art of Computer Programming, Vol. 2, §4.3.2 Modular Arithmetic — Constructive proof and the mixed-radix (Garner) alternative.
Related calculators
Modulo Calculator
Find a mod n for integers, negative numbers, and decimals with the quotient, remainder, division equation, congruence class, clock visual, and a clear explanation of floored vs truncated remainders.
Modular Exponentiation Calculator
Compute a^b mod n exactly for big numbers using square-and-multiply with every squaring and reduction tabulated, find a modular inverse a^-1 mod n with extended Euclid steps, or the ordinary multiplicative inverse (reciprocal) of a number.
Relatively Prime Calculator
Test whether numbers are relatively prime (coprime, gcd = 1) with every Euclidean division shown and the shared prime factors when they are not; a second mode computes Euler's totient φ(n), how many numbers from 1 to n are coprime to n, from the prime-factor product formula.
LCM Calculator
Find the least common multiple (LCM) of any list of whole numbers with three worked methods: listing multiples, the prime-factorization exponent table, and lcm(a, b) = a × b ÷ gcf(a, b) using Euclid's algorithm.
Remainder Calculator
Divide two whole numbers and get the quotient and remainder, the check equation a = b × q + r, the mixed-number, fraction, and decimal forms of the same division, and both sign conventions for negatives.
GCF Calculator
Find the greatest common factor (GCF, also called GCD or HCF) of any list of whole numbers with three worked methods: listing factors, the prime-factorization table, and Euclid's division algorithm.
Last updated: September 4, 2026