Chinese Remainder Theorem Calculator — solve simultaneous congruences

The Chinese remainder theorem calculator above solves a system of simultaneous congruences. You give it a list of remainders and moduli, and it returns the smallest non-negative integer that satisfies all of them at once, together with the modulus that describes every other solution. It handles the classic case where the moduli are pairwise coprime and the harder general case where they share factors, and it says plainly when no solution exists rather than returning a number that does not work.

Arb Digital publishes it because the theorem is one of the few genuinely ancient results still in daily use, and because the arithmetic behind it is worth seeing rather than trusting. The calculation runs on arbitrary-precision integers, so moduli far beyond the range of ordinary floating-point arithmetic are handled exactly. Our modulo calculator evaluates a single modulo operation; this page solves a whole system of them simultaneously, which is a different and much larger job.

What This Chinese Remainder Theorem Calculator Does

It merges the congruences one at a time. Starting from the first, it combines the running solution with each new congruence, checking at every step whether the two are compatible. Where the moduli are coprime, they are always compatible and the combined modulus is their product. Where they share a factor, compatibility is a real condition, and the tool tests it before proceeding.

The output is a pair: a remainder and a modulus, written as x ≡ r (mod M). That pair describes infinitely many integers, all differing by M, and the tool lists as many of them as you ask for. It also reports whether the moduli you entered are pairwise coprime, because that single fact determines whether the classical theorem applies directly or the generalised version is needed.

Every answer is verified. The bar panel recomputes the solution modulo each of your original moduli and shows the result beside the remainder you asked for. That is not decoration — it is the check that catches a mis-typed input immediately, and it means you never have to take the headline on trust.

How to Use It

1. Write one congruence per line as two numbers: the remainder first, then the modulus. The line "3 5" means x leaves remainder 3 when divided by 5.
2. Use any separator — a space, a comma or a tab. Blank lines and stray text are ignored.
3. Enter as many lines as you like. Two is the minimum for the theorem to say anything interesting; there is no practical upper limit.
4. Read the headline as x ≡ r (mod M), where M is shown in the first grid item.
5. Check the bars to confirm that the solution reproduces every remainder you entered.

The Formula and How It Is Calculated

The classical statement is this: if the moduli m₁, m₂, …, mₖ are pairwise coprime, then for any remainders a₁ through aₖ there is exactly one solution modulo the product of all the moduli. Wolfram MathWorld's page on the Chinese remainder theorem gives the classical construction, which builds the answer as a sum of terms, one per congruence, each engineered to be zero modulo every other one.

This tool uses the iterative merge instead, because it extends naturally to moduli that are not coprime. To combine x ≡ a₁ (mod m₁) with x ≡ a₂ (mod m₂), let g be the greatest common divisor of the two moduli. If a₂ − a₁ is not divisible by g, the two congruences contradict each other and no solution exists. Otherwise the extended Euclidean algorithm supplies integers p and q with m₁p + m₂q = g, and the merged solution is a₁ + m₁ × ((a₂−a₁)/g × p), reduced modulo the least common multiple of the two moduli.

Work the default through. The system x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) is the problem posed in Sun Tzu's Suanjing in roughly the third century. Merging the first two: g = 1, lcm = 15, and the numbers satisfying both are 8, 23, 38 and so on — that is x ≡ 8 (mod 15). Merging that with x ≡ 2 (mod 7): the candidates 8, 23, 38, 53, 68, 83, 98 give remainders 1, 2, 3, 4, 5, 6, 0 modulo 7, so 23 is the one that works. The answer is x ≡ 23 (mod 105), and 105 is 3 × 5 × 7. Check it: 23 = 7×3 + 2, 23 = 4×5 + 3, 23 = 3×7 + 2.

When the Moduli Share a Factor

The classical theorem says nothing about moduli with a common divisor, and most calculators simply refuse them. That is a shame, because the general case is both solvable and instructive. Two congruences with moduli sharing a factor g agree only if their remainders agree modulo g. If they do, a solution exists and is unique modulo the least common multiple rather than the product; if they do not, the system is genuinely contradictory.

Try x ≡ 2 (mod 4) together with x ≡ 4 (mod 6). Here g = 2, and 4 − 2 = 2 is divisible by 2, so a solution exists. The least common multiple is 12, and the answer is x ≡ 10 (mod 12). Check: 10 = 2×4 + 2 and 10 = 1×6 + 4. Note that the modulus is 12 and not 24 — the shared factor is counted once, which is exactly what the least common multiple does and the product does not. Our LCM and GCF calculator computes both quantities directly if you want to check them.

Now try x ≡ 1 (mod 2) with x ≡ 2 (mod 4). The first says x is odd; the second says x is even. No integer is both, and the tool returns a written explanation naming the two congruences that clash rather than a number. That behaviour is the point of the compatibility test: an unsolvable system should announce itself, not produce a plausible-looking wrong answer.

Why This Theorem Is Everywhere in Computing

The theorem is not a curiosity. It is the reason large-integer arithmetic can be split across small independent pieces. If you know a number's remainders modulo several coprime moduli, you know the number itself modulo their product — so a computation on a huge integer can be carried out separately on each small residue and reassembled at the end. That is the residue number system, and it makes the individual operations both smaller and independent, which suits parallel hardware.

The most widely deployed application is in RSA. Decryption with the private key is roughly four times faster when carried out separately modulo each of the two primes and recombined with the theorem, which is why essentially every real implementation stores the extra parameters needed to do exactly that. Secret sharing schemes, hash table designs, error-correcting codes and calendar calculations all lean on the same fact. Our modular inverse calculator computes the extended Euclidean step that sits inside every one of these constructions.

The historical route is worth knowing too. The problem in Sun Tzu's manual is a counting puzzle — an army counted off in threes, fives and sevens — and the general method was set out by Qin Jiushao in 1247. Gauss gave the modern statement in the Disquisitiones Arithmeticae in 1801. The theorem is roughly seventeen centuries older than the machines that now depend on it.

Reading the Answer Correctly

The result is a congruence class, not a single number. When the tool reports x ≡ 23 (mod 105), the solutions are 23, 128, 233 and so on upwards, and also −82, −187 and so on downwards. The smallest non-negative one is shown as the headline because that is the conventional representative, but it is not more correct than the others.

Two consequences follow. First, if your problem has a bounded range — "the smallest number over 1,000 that satisfies these" — you take the reported remainder and add whatever multiple of the modulus lands you in range. Second, if the combined modulus is smaller than you expected, the moduli shared factors. Comparing the reported modulus with the product of your moduli is the quickest test for that, and the coprime indicator in the grid says the same thing directly. Wolfram MathWorld's page on congruence covers the notation and the basic arithmetic rules the whole method rests on.

Common Mistakes to Avoid

• Writing the modulus before the remainder — the line "3 2" means x ≡ 3 (mod 2), which is not the same system as "2 3" and usually reduces to something trivial.
• Assuming the combined modulus is the product — it is the least common multiple, and those differ whenever the moduli share a factor.
• Applying the classical theorem to non-coprime moduli — the uniqueness statement does not hold there, and a solution may not exist at all.
• Treating the answer as a single number — it is a whole congruence class, and any member of it is an equally valid solution.
• Using a remainder larger than its modulus — it is not wrong, but reduce it first if you want the input to read the way a textbook writes it.

Related Free Tools From Arb Digital

Evaluate a single modulo operation with the modulo calculator, find a quotient and remainder with the remainder calculator, invert a residue with the modular inverse calculator, split a number into primes with the prime factorization calculator, or solve a linear system over the reals with the system of equations calculator. The full free online tools hub lists every mathematics tool we publish.

Frequently Asked Questions

This page explains a result in number theory for educational purposes. The cryptographic uses mentioned are described to give context and are not implementation guidance.