Chinese Remainder Theorem Calculator: One Number From Many Remainders
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
A Chinese Remainder Theorem calculator settles a riddle that has been in circulation for about seventeen centuries. Count a pile of objects in threes and 2 are left over; count the same pile in fives and 3 are left over; count it in sevens and 2 are left over. How many objects? The answer is 23, and the remarkable part isn’t that an answer exists — it’s that those three scraps of leftover information pin down the pile completely, to one number in every 105.
That is the whole theorem in one sentence, and it turns out to be load-bearing. The same result is what lets a server decrypt an RSA message four times faster than the naive route, and what lets competitive programmers reconstruct a giant number from a handful of small ones without ever storing the giant number.
An Army Counted in Threes, Fives and Sevens
The problem appears in the Sunzi Suanjing, a Chinese arithmetic manual written somewhere between the 3rd and 5th century. The text poses it, gives the answer 23, and moves on without much justification — the usual story is that a general counted his troops by having them form rows, since counting the leftovers in a formation of thousands is much faster than counting the men. Whatever the origin, the mathematics is exact:
Try 23 against each condition: 23 = 7×3 + 2, so remainder 2 modulo 3. 23 = 4×5 + 3, remainder 3. 23 = 3×7 + 2, remainder 2. All three hold. But 23 is not the only answer, and the mistake of reporting it as though it were costs marks in every exam. Add 105 and every remainder comes back unchanged, because 105 is divisible by 3, by 5 and by 7. So 128 works. So does 233, 338, 443, and — going the other way — −82. What the theorem delivers is a residue class, written x ≡ 23 (mod 105), not a single integer. If the leftovers themselves are what you need to compute, the modulo calculator handles those directly.
A general method took considerably longer to appear than the answer did. Qin Jiushao published one in 1247 under the name “the great extension”, and Gauss gave the version every textbook now prints in his 1801 Disquisitiones Arithmeticae. Between those dates the problem was mostly a party trick. The modern statement covers arbitrary systems, not just three congruences with small moduli.
Why the Answer Repeats Every 105
Here is the counting argument, and it’s worth following because it explains the coprimality condition instead of just stating it. A number modulo 3 has 3 possible remainders, modulo 5 it has 5, modulo 7 it has 7. That gives 3 × 5 × 7 = 105 possible remainder triples. There are also exactly 105 residue classes modulo 105. Now map each number in 0…104 to its triple. No two of them can produce the same triple — if they did, their difference would be divisible by 3, by 5 and by 7 at once, hence by 105, which is impossible for two distinct numbers under 105. So 105 inputs map to 105 outputs with no collisions, which forces the map to hit every triple exactly once.
Every possible combination of remainders is therefore achievable, and achievable in one way. That is a stronger claim than “a solution exists”, and it depends entirely on the moduli being pairwise coprime. Once they share factors the neat count collapses:
| Moduli | Remainder patterns | Patterns with a solution | Repeat period |
|---|---|---|---|
| 3, 5, 7 | 105 | 105 (100%) | 105 |
| 4, 6 | 24 | 12 (50%) | 12 |
| 6, 15 | 90 | 30 (33%) | 30 |
| 2, 3, 4, 5, 6, 7 | 5,040 | 420 (8%) | 420 |
Read the last two columns together: the number of solvable patterns always equals the repeat period, which is the least common multiple of the moduli. For coprime moduli the lcm equals the product and nothing is lost. For 2 through 7 the product is 5,040 but the lcm is only 420, so eleven out of every twelve remainder patterns you could write down are self-contradictory and have no solution at all. The classic basket-of-eggs puzzle — one egg left over in groups of 2, 3, 4, 5 and 6, none left over in groups of 7 — is one of the lucky patterns, and its answer is 301. Load that preset and the combined modulus tile reports 420 rather than 5,040.
Gauss’s Table: Three Numbers That Do the Whole Job
The classical construction builds the answer out of pieces that are deliberately blind to each other. Multiply all the moduli into M = 105. For each congruence take Mᵢ = M / nᵢ, which is divisible by every modulus except its own, then scale it by yᵢ = Mᵢ⁻¹ mod nᵢ so it lands on exactly 1 in its own congruence. Multiply by the remainder aᵢ and add everything up:
| aᵢ (mod nᵢ) | Mᵢ = 105 / nᵢ | Mᵢ mod nᵢ | yᵢ | aᵢ · Mᵢ · yᵢ |
|---|---|---|---|---|
| 2 (mod 3) | 35 | 2 | 2 | 140 |
| 3 (mod 5) | 21 | 1 | 1 | 63 |
| 2 (mod 7) | 15 | 1 | 1 | 30 |
| Total, then reduced mod 105 | 233 → 23 | |||
Check the first row against the second congruence to see the design: 140 = 28 × 5, so modulo 5 it contributes nothing, and the same holds modulo 7. Only the middle term speaks modulo 5. Each term is loud in one congruence and silent in the others, which is why the sum satisfies all three simultaneously.
The one genuinely fiddly column is yᵢ, and it is where hand-worked attempts go wrong. It is a modular inverse, not a fraction — you want the number that multiplies Mᵢ up to 1 modulo nᵢ. In row one that means solving 35y ≡ 1 (mod 3). Reduce 35 to 2 first, then 2 × 2 = 4 ≡ 1, so y = 2. Reducing before inverting saves real effort here, and for a modulus like 5 it turns a two-digit inversion into a single-digit one. This construction is also the reason the theorem demands coprime moduli: if Mᵢ and nᵢ shared a factor, that inverse would not exist and the table would stall on the fourth column.
What a Chinese Remainder Theorem Calculator Does Instead: Two Merges
Software rarely builds Gauss’s table. It folds the congruences together in pairs instead: solve the first two, replace them with the single congruence that captures both, then fold in the third. Sun Tzu’s system takes two merges.
Start with x ≡ 2 (mod 3). Bring in x ≡ 3 (mod 5). Anything satisfying the first has the form 2 + 3k, so 2 + 3k ≡ 3 (mod 5), which gives 3k ≡ 1 (mod 5) and k ≡ 2 (mod 5). Take k = 2 and you get x = 8, so the pair collapses to x ≡ 8 (mod 15). Now bring in x ≡ 2 (mod 7): numbers of the form 8 + 15k need 15k ≡ −6 (mod 7), which reduces to k ≡ 1 (mod 7), so k = 1 and x = 23. Two merges, no table, and the running modulus grows 3 → 15 → 105 as the information accumulates.
Both routes are traced in the calculator above — switch Method to trace to compare them on your own system. The merge route wins on scale, because each step is one gcd and one multiplication regardless of how many congruences remain, and it never needs the product of all moduli in one piece.
For a three-congruence homework problem, though, neither method beats sieving by hand — and the trick is to start from the largest modulus. List the numbers satisfying x ≡ 2 (mod 7): 2, 9, 16, 23. Check each against mod 5 = 3 and mod 3 = 2. You hit 23 on the fourth try. Starting from the smallest modulus instead means walking 2, 5, 8, 11, 14, 17, 20, 23 — twice the work, and the gap widens fast as the moduli grow, since the number of trials is capped by the combined modulus divided by the one you sieve on.
Moduli That Share a Factor Still Work — Sometimes
Most CRT calculators refuse any system whose moduli aren’t coprime. That refusal is overcautious: such systems often have solutions, they just need one extra test. Merging x ≡ r (mod M) with x ≡ a (mod n) succeeds exactly when gcd(M, n) divides a − r.
Take x ≡ 2 (mod 6) and x ≡ 8 (mod 15). The moduli share a factor of 3, so the classical construction is unavailable. The test: gcd(6, 15) = 3, and the gap 8 − 2 = 6 is divisible by 3. Solvable. The answer is x ≡ 8 (mod 30), where 30 is the lcm rather than the product 90. Both congruences secretly agree that x ≡ 2 (mod 3); they merely say it twice, and the overlap is exactly the factor 3 that the product would have double-counted.
Now change one digit: x ≡ 1 (mod 4) and x ≡ 2 (mod 6). The first forces x odd, the second forces it even. gcd(4, 6) = 2 does not divide 2 − 1 = 1, so the test fails, and no integer anywhere satisfies both — not a limitation of the method, a property of the system. Both cases are loaded as presets above so you can watch the merge table succeed and fail. This is also the situation where an answer that “looks fine” is most dangerous: a solver that skips the gcd test can return a number that satisfies the last congruence it processed and quietly violates an earlier one, which is precisely why the verification table checks the result against every row rather than the final one.
The Four-Fold Speedup Inside Every RSA Signature
RSA decryption computes m = cd mod n, where n = pq is 2048 bits and d is roughly the same size. Done directly, that is a modular exponentiation with 2048-bit operands: about 2048 squarings on numbers whose multiplication cost grows with the square of their length.
The private key holder knows p and q, so they can work in the two halves separately. Compute m₁ = cd mod (p−1) mod p and m₂ = cd mod (q−1) mod q, each with a 1024-bit modulus and a 1024-bit exponent, then recombine with CRT. Halving the operand length cuts each multiplication to a quarter of the cost and halves the number of squarings, so each half costs about an eighth of the full job. Two halves, and you land near a quarter of the original — the familiar figure of roughly 4× faster, and the reason RSA private keys are stored as five numbers (p, q, dP, dQ, qInv) rather than just d and n.
The recombination is a two-congruence CRT with the inverse precomputed: h = qInv · (m₁ − m₂) mod p, then m = m₂ + h·q. Load the RSA-CRT preset above and the merge table shows this exact shape on the toy key p = 61, q = 53 — two pieces mod 61 and mod 53 folding into one answer mod 3,233.
One warning, because it is a genuine and famous failure mode. If a hardware glitch corrupts just one of the two halves, the resulting signature is correct modulo one prime and wrong modulo the other — and gcd(m − m’, n) then hands an attacker the factorisation of n from a single faulty output. That is the Bellcore fault attack, published in 1997, and it is why production RSA implementations verify a CRT signature before releasing it. The same structural insight that makes CRT fast also makes a corrupted half catastrophic, which is a fair summary of why this seventeen-hundred-year-old counting trick still gets attention. If you would rather see the structure than the cryptography, the Euler phi calculator shows the same split-into-coprime-parts idea applied to counting instead of computing.
