chinese remainder theorem calculator

What this chinese remainder theorem calculator does

This chinese remainder theorem calculator solves systems of modular equations quickly and accurately. If your system looks like:

x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ a_k (mod n_k)

the calculator returns the smallest non-negative solution and the full solution class x ≡ r (mod M), where M is the least common period of all constraints (often the least common multiple of the moduli).

Quick refresher: the Chinese Remainder Theorem

Core idea

The Chinese Remainder Theorem (CRT) says that multiple remainders can determine a unique answer modulo a combined modulus. In the simplest case, when all moduli are pairwise coprime, there is always exactly one solution modulo the product of the moduli.

General case (important)

Many real problems include moduli that are not coprime. A solution still may exist, but only when the remainders are compatible. For two equations:

• x ≡ a (mod m)
• x ≡ b (mod n)

a solution exists if and only if a ≡ b (mod gcd(m, n)). This calculator automatically performs that check and tells you when no solution exists.

How to use the calculator

• Add each congruence as remainder a and modulus n.
• Click Calculate.
• Read the smallest solution and the general form x = r + Mk.
• Review the step list to see how congruences were merged.

Tip: negative remainders are fine. The tool normalizes them into standard form automatically.

Worked example

Try the default values:

• x ≡ 2 (mod 3)
• x ≡ 3 (mod 5)
• x ≡ 2 (mod 7)

The calculator returns x ≡ 23 (mod 105). That means 23 is the smallest solution, and every number of the form 23 + 105k also works.

When there is no solution

Not all modular systems are consistent. For example:

• x ≡ 1 (mod 2)
• x ≡ 0 (mod 2)

These two conditions conflict directly, so there is no integer x satisfying both. The calculator reports this immediately, rather than forcing an incorrect output.

Practical applications

Cryptography

CRT is heavily used in RSA implementations to speed up modular arithmetic operations.

Scheduling and cycle alignment

If events repeat with different periods, CRT helps find the next time all cycle conditions happen together.

Computer science and hashing

CRT supports residue number systems and decomposition of large computations into smaller modular parts.

Common input tips

• Modulus must be a non-zero integer.
• Use positive moduli for clarity (the tool converts negative moduli to positive).
• Very large integers are supported through BigInt arithmetic.
• If you add an empty row, fill both fields or remove the row.

FAQ

Does this calculator require pairwise coprime moduli?

No. It handles the general CRT case and checks compatibility automatically.

What form is the answer given in?

You get a smallest non-negative solution r and a modulus M, meaning all solutions are x = r + Mk for any integer k.

Can I use huge numbers?

Yes. This page uses JavaScript BigInt for exact integer arithmetic, making it useful for large modular systems.