What this calculator does
The Chinese remainder theorem answers an ancient puzzle: find a number leaving specified remainders on division by several different divisors. It has been used for over 1,500 years, originally to count soldiers without counting them individually.
With coprime moduli a solution always exists and is unique within their product. Leaving remainder 2 on division by 3 and remainder 3 on division by 5 gives x ≡ 8 modulo 15.
The formula
The extended Euclidean algorithm relates the two moduli. When their gcd divides the difference of the remainders, a solution exists and is unique modulo the lowest common multiple.
| Term | Meaning |
|---|---|
| Congruence | A statement that two numbers leave the same remainder on division by a modulus. |
| Coprime moduli | Moduli sharing no common factor, which guarantees a solution exists. |
| Modulus of the solution | The lowest common multiple, within which the answer is unique. |
The inputs explained
| Field | What to enter |
|---|---|
| a₁ (remainder mod n₁) | The remainder required modulo n₁. |
| n₁ (modulus) | The first modulus. |
| a₂ (remainder mod n₂) | The remainder required modulo n₂. |
| n₂ (modulus) | The second modulus. |
When to use it
Solving a remainder puzzle
The classic form of the problem the theorem was invented for.
Calendar and cycle problems
Two cycles of different lengths aligning is exactly this question.
Cryptography
RSA decryption is commonly accelerated using this theorem.
Worked examples
Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.
How does the second remainder move the answer?
The same first congruence against three second remainders.
Questions
Why is it called the Chinese remainder theorem?
Because the earliest known statement appears in a third-century Chinese text by Sun Tzu, phrased as a puzzle about a number leaving remainders 2, 3 and 2 on division by 3, 5 and 7. The general theorem came much later.
What if the moduli are not coprime?
A solution may still exist, but only if the gcd of the moduli divides the difference of the remainders. When it does, the answer is unique modulo their lowest common multiple rather than their product.
Why is the solution unique only modulo the lcm?
Because adding any multiple of the lowest common multiple leaves both remainders unchanged. There are infinitely many solutions, all differing by that amount, and the smallest non-negative one is reported.
How is it used in cryptography?
RSA decryption can be split into two smaller calculations modulo each prime factor and recombined with this theorem, which is several times faster than working with the full modulus directly.
For modular inverses, see the modular inverse calculator. For integer solutions to linear equations, see the linear Diophantine calculator.