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) |
What the Chinese remainder theorem is
The Chinese remainder theorem solves simultaneous congruences of the kind **“what number leaves 2 on division by 3, 3 by 5 and 2 by 7?”**. Provided the moduli are all coprime, exactly one solution exists within the range set by their product. This tool takes up to five congruences and returns the least non-negative solution along with the general one.
**Only the classical form is handled — the one where all the moduli are coprime.** If any two of them share a divisor greater than one the system cannot be solved this way, and an error says so; the generalised theorem for non-coprime moduli lies outside the scope. **Moduli must be integers of 2 or more**, and the remainders are normalised automatically into the range from zero up to their modulus, so values at or above the modulus, and negative ones, are accepted. The arithmetic runs on arbitrary-precision integers, so there is no limit on the number of digits.
How to use the calculator
- Enter the remainder and the modulus For each congruence, give the remainder a and the modulus n. They stand for x ≡ a (mod n).
- Add more congruences Use “add congruence” to line up as many as five. The more there are, the wider the range — the product of the moduli — over which the solution stays unique.
- Solve Press solve and you get the least non-negative solution together with the general solution modulo the product of the moduli.
- Follow the working For each congruence, Nᵢ (the product of the moduli with its own removed) and Mᵢ (the inverse of Nᵢ) are listed. They serve for checking a solution worked out by hand.
- Coprime moduli are required A message that the moduli are not coprime means two of them share a divisor — 4 and 6, for instance. Revisit the combination.
Tips for getting more out of it
- 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.
Where the theorem helps
Number theory exercises and exam practice
It serves for checking an answer worked by hand. Since Nᵢ and Mᵢ appear too, you can narrow down where a slip crept in.
Studying cryptographic algorithms
The CRT optimisation that speeds up RSA decryption applies this theorem directly. You can follow the mechanism in numbers.
Finding when cycles coincide
The times at which events of differing periods fall together can be written as simultaneous congruences.
Reproducing the classical problem
The “unknown number” of the Sunzi Suanjing — leaving 2 on division by 3, 3 by 5 and 2 by 7 — is 23 modulo 105. Enter it as it stands and see.
When you want the related number-theory tools
For inverses and congruences themselves, see modular arithmetic; for greatest common divisors, GCD and LCM; for factorisation, prime factorisation.
Terms about the Chinese remainder theorem
- Chinese remainder theorem (CRT)
- The theorem stating that a system of congruences with coprime moduli has a unique solution modulo their product.
- Congruence
- An expression of the form x ≡ a (mod n), saying that the remainder of x on division by n equals a.
- Modulus
- The number one divides by. Here it is restricted to integers of 2 or more.
- Coprime
- Two integers whose greatest common divisor is 1. The classical CRT requires that any two of the moduli be coprime.
- Pairwise coprime
- Of three or more numbers: that any two taken out of them are coprime. A set can have overall greatest common divisor 1 without being pairwise coprime.
- Modular inverse
- The x satisfying a·x ≡ 1 (mod n). In the CRT it appears when finding Mᵢ, the inverse of Nᵢ.
- Extended Euclidean algorithm
- The algorithm that yields the Bézout coefficients alongside the greatest common divisor. It is what computes a modular inverse.
- General solution
- The least non-negative solution together with every integer multiple of the product of the moduli added to it, written in the form x ≡ 23 (mod 105).
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.