Chinese Remainder Theorem Calculator
Enter a system of congruences — x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) — and get the single value of x that satisfies all of them, with every merge step shown. Moduli that share factors are handled too, and numbers hundreds of digits long stay exact.
- Non-coprime moduli supported
- Exact arbitrary-precision maths
System of Congruences Solver
LiveThe solution and the modulus it repeats on.
- Combined modulus (lcm)
- —
- Pairwise coprime?
- —
The congruence merge, step by step
Every panel updates as you edit the congruences. The step list merges them two at a time, the pair check explains any failure, and the classical table appears whenever the moduli are pairwise coprime.
How the solution was built
Pairwise coprime and compatibility check
A pair with a gcd of 1 is coprime. A pair sharing a factor still works whenever both remainders agree modulo that factor, and clashes when they do not.
Classical construction table
x = Σ rᵢ · Mᵢ · yᵢ (mod M), where Mᵢ = M / mᵢ and yᵢ is the inverse of Mᵢ modulo mᵢ.
What Is the Chinese Remainder Theorem?
The Chinese Remainder Theorem (CRT) states that a set of remainders against pairwise coprime divisors pins down a single number. Knowing what an unknown number leaves when divided by 3, by 5 and by 7 is enough to identify it exactly, modulo 3 × 5 × 7 = 105.
Sun Tzu recorded the first version in the third-century text Sun Tzu Suan Ching, as a puzzle: find a number leaving 2 when divided by 3, 3 when divided by 5, and 2 when divided by 7. The answer is 23.
Two ideas carry the whole theorem. A remainder r of a divided by b is the integer between 0 and b − 1 satisfying a = k·b + r for some integer k — dividing 17 by 5 fits three 5s and leaves 2, so 17 = 3·5 + 2. A congruence a ≡ b (mod n) says a and b leave the same remainder against n, which makes their difference a multiple of n.
Congruences behave like ordinary equations in most respects. Adding or subtracting a number on both sides is safe, and so is multiplying by an integer. Dividing is not, which is exactly why modular inverses — and the Euclidean algorithm that produces them — appear inside the theorem's proof.
Each congruence on its own leaves infinitely many candidates. Stacking them narrows the field, and the sieve below shows the narrowing for 2 congruences: the numbers leaving 2 against 3, the numbers leaving 3 against 5, and the single column where the 2 rows agree.
Both rows land on 8, and on nothing else below 15 — so x ≡ 8 (mod 15).
How to Use the Chinese Remainder Theorem Calculator
To use the Chinese Remainder Theorem calculator, fill in one row per congruence and read the solution. The answer and the working appear together in 4 steps:
- Enter the remainder in the left box of each row. Negative values are accepted and normalised into the range 0 to m − 1.
- Enter the modulus in the right box. Moduli of 1 or more are accepted, coprime or not.
- Add rows with the button below the list. Two congruences are the minimum and 12 the maximum.
- Read x ≡ R (mod M), where R is the smallest non-negative solution and M is the least common multiple of the moduli.
The calculator reports 5 results for every system: the smallest non-negative solution, the combined modulus, a pairwise coprime verdict, the family of all solutions in the form R + Mk, and a check line confirming the answer against every congruence you entered. A contradictory system returns the clashing pair by name rather than a wrong number.
Arithmetic runs in arbitrary-precision integers, so moduli with hundreds of digits stay exact with nothing rounded. That matters for cryptography, where CRT recombines RSA decryptions carried out modulo p and modulo q separately — roughly 4 times faster than working modulo n directly.
Chinese Remainder Theorem Formula
The Chinese Remainder Theorem formula is x = Σ rᵢ · Mᵢ · yᵢ (mod M), built from the product of the moduli and one modular inverse per congruence.
Given x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂), …, x ≡ rₖ (mod mₖ) with m₁, m₂, …, mₖ pairwise coprime: M = m₁ · m₂ · … · mₖ the product of every modulus Mᵢ = M / mᵢ everything except mᵢ yᵢ = Mᵢ⁻¹ (mod mᵢ) the inverse of Mᵢ modulo mᵢ x = Σ rᵢ · Mᵢ · yᵢ (mod M) unique modulo MThe construction works for 1 reason: each term rᵢ·Mᵢ·yᵢ leaves rᵢ against mᵢ and leaves 0 against every other modulus, since Mᵢ already contains those moduli as factors. Adding the terms therefore satisfies all k congruences at once.
Finding each yᵢ needs the extended Euclidean algorithm and Bézout's identity. Bézout's identity states that for non-zero a and b there exist integers k and l with k·a + l·b = gcd(a, b). Running the Euclidean algorithm on 1785 and 546 gives the remainder chain 147, 105, 42, 21, 0 — so gcd(1785, 546) = 21 — and back-substituting through those 5 equations produces −11·1785 + 36·546 = 21, with k = −11 and l = 36. The extended Euclidean algorithm steps tool runs that whole chain for any pair.
Setting a = mᵢ and b = Mᵢ turns Bézout's identity into the inverse the formula needs. Coprime moduli make gcd(mᵢ, Mᵢ) = 1, so the identity reads u·mᵢ + v·Mᵢ = 1, and reducing modulo mᵢ leaves v·Mᵢ ≡ 1 — which makes v the inverse yᵢ.
When Does the Chinese Remainder Theorem Apply?
The Chinese Remainder Theorem applies whenever the moduli are pairwise coprime, meaning every pair has a gcd of 1. Under that condition a solution always exists and is unique modulo the product of the moduli.
Pairwise coprime is stricter than it sounds. The moduli 3, 5 and 7 pass, since gcd(3,5) = gcd(3,7) = gcd(5,7) = 1. The moduli 4, 6 and 9 fail on every pair, and 2, 3 and 4 fail on the single pair (2, 4) even though the other 2 pairs are fine. One failing pair is enough to put the classical formula out of reach.
Shared factors do not end the matter. The generalised condition is weaker and still exact:
A system is solvable ⟺ rᵢ ≡ rⱼ (mod gcd(mᵢ, mⱼ)) for every pair and the solution is then unique modulo lcm(m₁, m₂, …, mₖ)That condition collapses to the classical one when the moduli are coprime, since gcd = 1 makes every pair agree automatically and the lcm equals the product. The calculator applies the general test on every run, which is what lets it accept non-coprime input.
x ≡ 2 (mod 3) x ≡ 3 (mod 5) gcd(3, 5) = 1 → x ≡ 8 (mod 15)
x ≡ 3 (mod 4) x ≡ 5 (mod 6) gcd(4, 6) = 2 3 mod 2 = 1, 5 mod 2 = 1 ✓ → x ≡ 11 (mod 12)
x ≡ 1 (mod 4) x ≡ 2 (mod 6) gcd(4, 6) = 2 1 mod 2 = 1, 2 mod 2 = 0 ✕ → no solution
Solving Simultaneous Congruences
To solve simultaneous congruences, merge them 2 at a time until 1 congruence remains. Each merge folds a pair into a single statement modulo the lcm of their moduli, and the count of congruences drops by 1 every round.
The merge takes 3 steps. Write the first congruence as x = r + m·t, substitute it into the second to get m·t ≡ r′ − r (mod m′), and solve that for t with the modular inverse. Folding x ≡ 8 (mod 15) into x ≡ 2 (mod 7) gives 8 + 15t ≡ 2 (mod 7), which reduces to 1 + t ≡ 2, so t ≡ 1 and x = 8 + 15 = 23.
The classical formula reaches the same 23 through the construction table instead of the merge chain:
| i | rᵢ | mᵢ | Mᵢ = 105 / mᵢ | yᵢ = Mᵢ⁻¹ mod mᵢ | rᵢ · Mᵢ · yᵢ |
|---|---|---|---|---|---|
| 1 | 2 | 3 | 35 | 2 | 140 |
| 2 | 3 | 5 | 21 | 1 | 63 |
| 3 | 2 | 7 | 15 | 1 | 30 |
| Sum, then reduce modulo M = 105 | 233 → 23 | ||||
A second worked example puts the theorem on a counting problem. A bag of sweets divides among 3 children with 1 left over, among 4 children with 2 left over, and among 5 children with 3 left over. Written as congruences that reads x ≡ 1 (mod 3), x ≡ 2 (mod 4), x ≡ 3 (mod 5), with M = 3 × 4 × 5 = 60. The solution is x ≡ 58 (mod 60), so the smallest possible bag holds 58 sweets — and 58 ÷ 3 leaves 1, 58 ÷ 4 leaves 2, 58 ÷ 5 leaves 3, exactly as stated.
Every solvable system produces an infinite family spaced one modulus apart:
The theorem earns its keep in 4 places. RSA decryption splits one exponentiation modulo n = pq into two smaller ones and recombines them with CRT. Secret sharing schemes such as Mignotte and Asmuth-Bloom hand out residues against different moduli, so enough shares reconstruct the secret and too few reveal nothing. Calendar and cycle problems find when repeating events coincide. Residue number systems represent one large integer as several small residues, letting additions and multiplications run in parallel with no carries.
Common Chinese Remainder Theorem Mistakes
There are 5 common Chinese Remainder Theorem mistakes, and every one of them is caught by testing the answer against each original congruence.
Test every pair separately. The moduli 2, 3 and 4 share no factor across all 3 at once, and the pair (2, 4) still has a gcd of 2 — enough to break the classical formula.
Invert Mᵢ modulo mᵢ, not mᵢ modulo Mᵢ. The formula needs yᵢ with Mᵢ·yᵢ ≡ 1 (mod mᵢ), and swapping the 2 produces a value that satisfies none of the congruences.
m₁ = 3, M₁ = 35 y₁ = 3⁻¹ mod 35 = 12
m₁ = 3, M₁ = 35 y₁ = 35⁻¹ mod 3 = 2
Add the modulus until the answer lands between 0 and M − 1. The candy system produces −122 from the raw sum, and adding 60 three times gives the reported answer of 58. Both describe the same residue class, and only 1 of the 2 reads as a count of sweets.
x = 1(−20) + 2(−15) + 3(−24) = −122 "mom bought −122 sweets"
x = −122 + 3 × 60 = 58 58 ÷ 3 R1, ÷ 4 R2, ÷ 5 R3 ✓
Reduce modulo the lcm rather than the product, when any pair shares a factor. x ≡ 3 (mod 4) with x ≡ 5 (mod 6) is unique modulo lcm(4, 6) = 12, not modulo 24 — reporting mod 24 claims 2 distinct solutions where 1 exists.
Check the pairs before solving. x ≡ 1 (mod 4) and x ≡ 2 (mod 6) contradict each other, since the first forces x odd and the second forces x even. A method that grinds on regardless returns a number satisfying neither congruence.
Check any Chinese Remainder Theorem answer in 1 pass: divide the solution by each modulus and confirm the remainders match the ones you entered. 23 ÷ 3 leaves 2, 23 ÷ 5 leaves 3, and 23 ÷ 7 leaves 2, which settles the system. The remainder calculator runs any of those divisions on its own, and the modulo operator calculator handles the sign conventions once negative remainders enter.