Chinese Remainder Theorem Calculator

Understanding the Chinese remainder theorem calculator — concept and principle

The Chinese remainder theorem (CRT) answers a question of the form "which number leaves remainder a₁ when divided by n₁, remainder a₂ when divided by n₂, and so on?". When the moduli are pairwise coprime there is exactly one answer between 0 and N − 1, where N is the product of the moduli, and every other answer differs from it by a multiple of N. It is used in number theory, calendar and cycle problems, and RSA decryption speed-ups.

How it is calculated

The system is x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), …, x ≡ aₖ (mod nₖ). The calculator uses successive substitution:

1. Start with x = 0 and step N = 1.
2. For each congruence, try t = 0, 1, 2, … until (x + N·t) mod nᵢ equals aᵢ mod nᵢ. Then set x ← x + N·t and N ← lcm(N, nᵢ), which is N·nᵢ when they are coprime; x is reduced mod N each step.
3. If no t below nᵢ works, the system has no solution (this can only happen when moduli share a factor).

The answer is shown as x (mod N).

The principle

Adding a multiple of N to x does not change any of the remainders already satisfied, because N is divisible by every earlier modulus. So the method can fix one congruence at a time without breaking the previous ones. Because N and the new modulus nᵢ share no factor, the values x, x + N, x + 2N, …, x + (nᵢ − 1)N all leave different remainders mod nᵢ, so exactly one of them hits aᵢ.

Worked example

1. Inputs: remainders 2, 3, 2 and moduli 3, 5, 7. This is the classic problem from the Chinese text Sunzi Suanjing.
2. x ≡ 2 (mod 3): from x = 0, N = 1, t = 2 works, so x = 2, N = 3.
3. x ≡ 3 (mod 5): try 2, 5, 8. 8 mod 5 = 3, so t = 2, x = 8, N = 15.
4. x ≡ 2 (mod 7): try 8 (remainder 1), then 23 (remainder 2), so x = 23, N = 105.
5. Result: x ≡ 23 (mod 105). Other solutions: 128, 233, …

How to read the result

"23 (mod 105)" means the smallest non-negative solution is 23 and adding or subtracting 105 gives all the others. If you need a solution in a particular range, add multiples of N until you are inside it. Check the answer by dividing it by each modulus.

Common mistakes

• Using moduli that share a factor, such as 4 and 6. The basic theorem then does not apply, and a system may have no solution.
• Entering a different number of remainders and moduli.
• Forgetting that the answer is a whole class of numbers, not a single value.

Frequently asked questions

What does pairwise coprime mean?

Every pair of moduli has greatest common divisor 1. For example 4, 9 and 25 are pairwise coprime even though none of them is prime.

Is there a formula instead of trial?

Yes. x = Σ aᵢ·Mᵢ·yᵢ mod N, where Mᵢ = N/nᵢ and yᵢ is the modular inverse of Mᵢ mod nᵢ, found with the extended Euclidean algorithm.

Why is it called Chinese?

The earliest known statement appears in the Sunzi Suanjing (around the 3rd to 5th century); Qin Jiushao gave a general method in 1247.

Sources: Sunzi Suanjing (The Mathematical Classic of Sunzi), Volume 3, Problem 26 · G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press