What does "pairwise coprime" mean?

Every pair of moduli must share no common factor other than 1. For example, moduli 3, 5, and 7 are pairwise coprime, but 4 and 6 are not because gcd(4,6) = 2. The CRT guarantees a unique solution only when this condition holds.

What if the moduli are not coprime?

The tool will show an error identifying which pair of moduli violates the condition. A solution may still exist, but it requires a more general algorithm (extended CRT) and is not always unique.

What is the range of the solution?

The tool returns the smallest non-negative x in the range [0, M) where M is the product of all moduli. Every other solution is of the form x + k·M for any integer k.

Can remainders be larger than their modulus?

The remainder r is automatically reduced modulo m, so entering r = 10 with m = 3 is treated as r = 1. The tool shows the reduced value in the step-by-step output.

How many congruences can I enter?

The tool supports 2 to 6 congruences. For most practical and academic problems this is more than enough.

How is this different from Wolfram Alpha?

Both compute the same answer, but this calculator shows the full step-by-step CRT derivation — the partial products Mi, each modular inverse, and the weighted sum — so you can follow the method, not just read the final value. It runs entirely in your browser with no query limits.

Chinese Remainder Theorem Calculator

Name: Chinese Remainder Theorem Calculator
Availability: InStock
Author: Nham Vu

Enter up to 6 congruences and instantly find the unique solution x via the Chinese Remainder Theorem.

System of Congruences

Enter x ≡ r (mod m) for each row. All moduli must be pairwise coprime.

Examples

Enter congruences on the left and press Solve.

Unique Solution

Step-by-step derivation

Step 1 — Compute M (product of all moduli)

Step 2 — Partial products Mi = M / mi

i	mi	ri	Mi = M/mi

Step 3 — Modular inverses yi ≡ Mi⁻¹ (mod mi)

i	Mi	mi	yi = Mi⁻¹ mod mi	ri × Mi × yi

Step 4 — Sum and reduce mod M

Summary

Enter up to 6 congruences and instantly find the unique solution x via the Chinese Remainder Theorem.

How it works

Enter at least 2 rows of remainder r and modulus m (e.g. r=2, m=3 means x ≡ 2 mod 3).
Click "Solve" — the tool checks that all moduli are pairwise coprime.
For each congruence the tool computes the partial product Mi = M / mi and its modular inverse.
The solution is x = Σ ri × Mi × Mi⁻¹ (mod M), reduced to the range [0, M).
All intermediate values are shown so you can follow every step.

Use cases

Solving number theory homework and competition problems.
Cryptography: combining partial results from smaller moduli (RSA-CRT optimisation).
Calendar and scheduling puzzles that reduce to simultaneous remainders.
Checking understanding of the CRT proof by inspecting each intermediate step.
Computer science: fast multi-precision arithmetic via the CRT representation.
Puzzle solving: "What is the smallest number that leaves remainder a when divided by b?"

Frequently Asked Questions

Last updated: 2026-06-10 · Reviewed by Nham Vu