Chinese Remainder Theorem (CRT) Calculator — Solve Simultaneous Congruences
Solve a system of simultaneous congruences x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)... with the Chinese Remainder Theorem. Automatically checks that the moduli are pairwise coprime and returns the smallest non-negative solution plus the general solution.
Worked example: the "unknown number" problem from the Sunzi Suanjing
A classic problem from the Sunzi Suanjing (Sun Tzu's Mathematical Classic), a Chinese arithmetic text dating to roughly the 3rd–5th century, often cited as the origin of the Chinese Remainder Theorem. The question "What number leaves a remainder of 2 when divided by 3, a remainder of 3 when divided by 5, and a remainder of 2 when divided by 7?" has the answer 23, modulo 105.
| Condition 1 | x ≡ 2 (mod 3) |
|---|---|
| Condition 2 | x ≡ 3 (mod 5) |
| Condition 3 | x ≡ 2 (mod 7) |
| Solution | x ≡ 23 (mod 105) |
Tips
- If the moduli (nᵢ) are not pairwise coprime you'll get an error — for example mod 4 and mod 6 share a factor of 2, so this calculator can't solve that system (it would require the generalized CRT).
- You don't need to reduce the remainder aᵢ yourself first: even if it's negative or greater than nᵢ, the calculator normalizes it to mod nᵢ internally before solving.
- You can add between 2 and 5 congruences. This is handy for puzzles that require a number to satisfy three or more periodic conditions at once, like the classic "guess the number of soldiers" riddle.
- The general solution is shown as x ≡ result (mod N): adding any multiple of N to the result still satisfies every original congruence.
Frequently Asked Questions
Side Note — From a 3rd-century arithmetic text to speeding up RSA encryption
The Chinese Remainder Theorem traces back to a problem in the Sunzi Suanjing, a Chinese arithmetic classic thought to date from roughly the 3rd to 5th century CE. Its famous "unknown number" puzzle — "find a number that leaves remainders of 2, 3, and 2 when divided by 3, 5, and 7 respectively" — already captured the essential idea behind the modern theorem: reconstructing an unknown number from several remainders of division.
One of the most practical modern applications of the Chinese Remainder Theorem is speeding up RSA decryption. RSA decryption requires raising a large number to a power modulo a composite n = p × q, where p and q are large primes. Instead of working modulo n directly, CRT lets you perform the computation independently modulo p and modulo q and then recombine the results — a technique known as CRT-RSA that can theoretically speed up decryption by close to a factor of four, and is implemented in many cryptographic libraries.
This tool supports the classic form of the theorem, which requires all moduli to be pairwise coprime. When the moduli share common factors (for example mod 4 and mod 6), a solution can sometimes still exist, but determining and computing it requires the generalized Chinese Remainder Theorem, which is outside the scope of this tool.