One number that satisfies every congruence at once — or proof that none does.
A system of congruences
Coprime moduli or not.
x ≡
(mod
)
x ≡
(mod
)
x ≡
(mod
)
x ≡ 23 (mod 105)
23
The smallest non-negative solution. Every solution is 23 plus a multiple of 105, so there are infinitely many and this is the one they are all measured from.
Smallest solution
23
non-negative
Repeats every
105
the product of the moduli
Moduli pairwise coprime?
yes
the classical statement applies
Next few solutions
128, 233, 338
each one modulus further on
Merging them one at a time
Each congruence folded into the running solution, with the combined modulus and the reason
Step
Congruence added
Combined
Why
1
x ≡ 2 (mod 3)
x ≡ 2 (mod 3)
The first congruence, taken as it stands.
2
x ≡ 3 (mod 5)
x ≡ 8 (mod 15)
3 and 5 are coprime, so the two congruences merge into one modulo their product.
3
x ≡ 2 (mod 7)
x ≡ 23 (mod 105)
15 and 7 are coprime, so the two congruences merge into one modulo their product.
The answer put back into every congruence
23 mod 3 = 2, and the congruence asks for 2
23 mod 5 = 3, and the congruence asks for 3
23 mod 7 = 2, and the congruence asks for 2
Every congruence above is re-checked against the answer rather than assumed — the verification is computed, not claimed.
What this tool shows
A number leaves 2 when divided by 3, 3 by 5 and 2 by 7. The answer is 23, and it repeats every 105. This page merges the congruences one at a time and puts the answer back into each of them, so the solution arrives already checked.
The smallest solution to a system of congruences
The modulus it repeats on
The merge, one congruence at a time
Whether the moduli are pairwise coprime
Systems whose moduli share factors
Why a contradictory system has no solution
Any number of congruences Each one checked back Non-coprime moduli too The merge shown step by step
Exact; every congruence re-checked against the answer.
Updated 7 September 2026 · Works in any browser, no installation
Merge the congruences two at a time. Take the first as it stands, then fold in the next by finding how far to step along the first modulus to satisfy the second. Repeat. For the classic system — 2 mod 3, 3 mod 5, 2 mod 7 — the answer is 23, and every solution is 23 plus a multiple of 105.
At a glance
Formula shown
For pairwise coprime moduli the system has exactly one solution modulo the product of the moduli. When moduli share factors, a solution exists if and only if every pair of congruences agrees modulo their gcd; it is then unique modulo the least common multiple rather than the product.
Scenario support
A counting puzzle with several leftover conditions; reconstructing a value from its residues in modular arithmetic; scheduling something that repeats on two cycles at once.
Educational estimate
Planning support from the values you enter — not professional advice.
The problem it is named for
The theorem takes its name from a problem in Sun Tzu’s Mathematical Manual, written somewhere between the third and fifth century: a number leaves 2 when divided by 3, 3 when divided by 5, and 2 when divided by 7. What is it?
The answer is 23, and the general solution is 23 + 105k. What makes the result a theorem rather than a puzzle is the guarantee: for any set of pairwise coprime moduli, and any remainders you like, a solution always exists and is unique up to the product.
That is a strong statement. You may specify the remainder independently for each modulus and never create a contradiction — provided the moduli share no factors.
How the merge works
The formula most textbooks give computes everything at once from the product of the moduli. This page merges pairwise instead, which is the same answer reached in a way you can follow.
Start with x ≡ 2 (mod 3). Every candidate is 2, 5, 8, 11, 14, 17, 20, 23. Now impose x ≡ 3 (mod 5): of those, 8 and 23 qualify, and they differ by 15 — so the merged congruence is x ≡ 8 (mod 15).
Impose x ≡ 2 (mod 7) on that, and 23 is the survivor, now modulo 105. Three congruences, two merges, and each step is checkable on its own.
Pairwise merging is also what makes non-coprime moduli work, since each merge only has to reconcile two congruences rather than assume the whole set is independent.
When the moduli are not coprime
The classical statement requires pairwise coprime moduli. Systems that fail that test are not automatically unsolvable — most textbooks simply do not cover them.
Take x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 4). Here 2 and 4 share a factor. But the two congruences agree about it: both ask for an odd number. So the system solves, giving x ≡ 11 (mod 12) — modulo the LCM, not the product 24.
The general condition is that every pair must agree modulo their gcd. When they do, the merged solution is unique modulo the least common multiple; when they do not, nothing satisfies both.
The page reports whether the moduli were pairwise coprime, and solves either way.
When there is no solution at all
x ≡ 0 (mod 4) and x ≡ 1 (mod 6) have no solution, and it is worth seeing exactly why.
The moduli share the factor 2. The first congruence forces x to be even; the second forces it to be odd. Reduced modulo 2, one asks for 0 and the other for 1, and no integer is both.
This is the general test. Two congruences are compatible when their remainders agree modulo the gcd of their moduli. The page performs that check on every merge and, when it fails, reports the two residues that disagree rather than a bare failure.
Where it is used
Speeding up RSA. A private-key operation modulo n = pq can be done separately modulo p and modulo q and recombined with the theorem — roughly four times faster, since the numbers are half the size. Every serious RSA implementation does this.
Big-number arithmetic. Compute modulo several small primes in parallel, then reconstruct the true value. Computer algebra systems use it to avoid enormous intermediates.
Secret sharing and error correction. Splitting a value into residues gives redundancy: enough residues rebuild it, and too few reveal nothing.
Calendars and cycles. Anything that repeats on two coprime periods at once — a 7-day week against a 12-year cycle, say — is a CRT problem in disguise.
Why the solutions repeat
A system of congruences never has just one solution. If 23 works, so does 128, and 233, and −82.
Adding the combined modulus changes nothing about any individual congruence, because the combined modulus is a multiple of each one. 105 is divisible by 3, 5 and 7, so adding it leaves every remainder untouched.
So the answer is a family: one representative plus every multiple of the combined modulus. The page shows the smallest non-negative member and the next few, because “23” on its own understates what was proved.
Sources and methodology
The theorem and its computational use are both standard — these are the references.
Method. The congruences are merged one pair at a time rather than through the product formula, which is what allows moduli that share factors: each merge checks that the difference of the remainders is divisible by the gcd, uses the extended Euclidean algorithm to find the step, and combines modulo the least common multiple. Every original congruence is then evaluated against the answer and the result displayed, so the verification is computed rather than asserted. The suite compares the answer with a brute-force scan of the combined range on three hundred two-congruence systems. That engine is verified on every change against 69 hand-written assertions, including that every solution satisfies every one of its own congruences across three thousand generated systems, and that the answer matches a brute-force scan on three hundred more. The count and the per-case breakdown are published on the formula verification page.
Related calculators
Where this goes next:
ModuloAll three conventions at once, because −7 mod 3 is −1 in JavaScript and 2 in Python and a page that gives only one of those is wrong for half its readers.
Modular InverseThe number that undoes a multiplication modulo n, from the extended Euclidean algorithm — or the shared factor that proves no such number exists.
CoprimeSet coprimality and pairwise coprimality are different conditions: 6, 10 and 15 have gcd 1 and not one coprime pair. Both are reported, with the offending pairs named.
LCMThe least common multiple of two to six numbers, with the prime table that produces it, the multiples themselves, and how far counting would have had to go.
RemainderQuotient, remainder and the multiplication that checks them — plus the repeated subtraction that shows why a division has to stop.
Modular Exponentiation7^128 mod 13 without ever building the 109-digit power. Square-and-multiply is shown one exponent bit at a time, with the count of multiplications it saved.
Whether your moduli meet the classical pairwise condition is a separate question, and the Coprime Calculator answers it directly — including the case where a set is coprime but no pair inside it is.
Educational use disclaimer
This is an educational tool. The arithmetic is exact; a system with no solution is reported as such, with the residues that contradict each other, rather than being forced to an answer.
Published the Chinese Remainder Theorem page handling moduli that are not pairwise coprime, which the classical statement excludes and most tools simply refuse.
The congruences are merged pairwise rather than through the product formula, so each step can be checked on its own and a shared factor is handled where it arises.
A contradictory system is reported with the two residues that disagree, rather than as a bare failure.
Add this calculator to your site
Responsive embed — and private: nothing your visitors type leaves their browser.