chinese remainder calculator

What this Chinese remainder calculator does

The Chinese Remainder Theorem (CRT) helps you solve systems where one unknown number must satisfy several remainders at once. For example, if a number leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7, CRT finds the smallest number that fits all three conditions.

This page gives you a practical calculator for those systems. It computes:

• The smallest non-negative solution x
• The combined modulus M so that all solutions are x + kM
• Step-by-step merge details for each congruence
• A clear “no solution” explanation when conditions conflict

How to use the calculator

1) Enter each congruence

Each row is one condition: x ≡ residue (mod modulus). Example row: residue = 3, modulus = 5 means x leaves remainder 3 when divided by 5.

2) Add or remove rows as needed

Use Add Congruence for larger systems. You can solve two equations or dozens, depending on your use case.

3) Click Calculate

The solver combines equations one pair at a time using the extended Euclidean algorithm. If the system is consistent, you’ll get a single compact result.

Example problems

Classic coprime example

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

Solution: x ≡ 23 (mod 105). So 23, 128, 233, and 338 all satisfy the full system.

Non-coprime moduli with a solution

• x ≡ 2 (mod 6)
• x ≡ 8 (mod 14)

A solution exists because the difference in residues is compatible with the gcd of the moduli. The calculator handles this automatically.

Non-coprime moduli with no solution

• x ≡ 1 (mod 4)
• x ≡ 2 (mod 6)

Here the conditions conflict. The tool will report no solution and explain why.

Why CRT is useful in real life

• Cryptography: RSA acceleration and modular arithmetic workflows
• Scheduling: finding repeated alignments of cycles and periodic events
• Computer science: hash structures, residue number systems, and optimization
• Math education: a concrete way to understand modular equations

Tips for reliable input

• Use integers only (positive or negative residues are both fine)
• Use non-zero positive moduli
• Large values are supported through JavaScript BigInt arithmetic
• If you see “no solution,” verify that your congruences are logically compatible

Quick refresher: theorem statement

When moduli are pairwise coprime, a system of congruences has exactly one solution modulo the product of those moduli. In the generalized case (not necessarily coprime), a solution exists only when residues agree on shared divisibility constraints. This calculator checks those constraints as it combines each equation.