How this instrument works
Two different remainder conditions can pin down a single hidden number. The Chinese Remainder Theorem says that whenever the two moduli share no common factor, exactly one such number exists between zero and their product. Ask for whatever leaves remainder r1 after division by m1, and also leaves remainder r2 after division by m2, and there is one answer within that range, not several — every other number satisfying both conditions is just that answer plus a multiple of m1 times m2.
The problem is centuries old. A version of it turns up in an ancient Chinese mathematical text traditionally credited to a scholar known as Sun Tzu, compiled long before anyone wrote the result as a tidy algebraic formula. Its reach turned out to be wide: RSA decryption splits one large exponentiation into two smaller ones under this exact theorem to save real computing time, and calendar puzzles reduce to precisely this two-condition setup — a delivery repeating every three days lining up against a festival repeating every five.
This sheet leans on a shortcut rather than a manual search through candidates. It borrows the same modular-inverse trick built for this site's Inverse Modulo page — raising a value to a power and reducing it, courtesy of Fermat's Little Theorem — as one internal ingredient, not as the final output. That neighboring page hands back a single inverted number, and the Fermat check on the Prime Number page tests one candidate for primality; this page asks something else altogether: given two remainder conditions on two separate moduli, what single number, taken modulo their product, satisfies both?
- Enter the first remainder into Remainder mod m1 (r1), and its modulus into First prime modulus (m1).
- Enter the second remainder into Remainder mod m2 (r2), and its modulus into Second prime modulus (m2).
- Confirm m1 and m2 share no common factor — the guarantee of one clean answer depends on that.
- Read Solution (x, mod m1×m2): the single number satisfying both remainder conditions together.
- Check it by hand: divide x by m1 and confirm the remainder is r1, then divide by m2 and confirm r2.
Worked example — remainder 2 mod 3 and remainder 3 mod 5
Set Remainder mod m1 (r1) to 2, First prime modulus (m1) to 3, Remainder mod m2 (r2) to 3, and Second prime modulus (m2) to 5. Solution (x, mod m1×m2) comes back as 8. Check it directly: 8 divided by 3 leaves a remainder of 2, matching r1, and 8 divided by 5 leaves a remainder of 3, matching r2 — both conditions land on that same 8, and since 3 and 5 share no factor, 8 is the only fit below their product, 15.
A second case shows what happens when the two conditions already agree: set both remainders to 1 under the same pair of moduli, 3 and 5, and the returned x is simply 1 — nothing smaller fits both, so nothing needed reconciling. A third case, remainder 0 mod 3 paired with remainder 2 mod 7, returns x = 9: divide 9 by 3 and nothing is left over, divide 9 by 7 and 2 remains, and 9 is the unique fit below the product of 3 and 7, which is 21.
Questions
What does the Chinese Remainder Theorem actually solve?
It finds the one number, between zero and the product of two moduli, that satisfies two separate remainder conditions at the same time. Given remainder 2 under modulus 3 and remainder 3 under modulus 5, that number is 8 — nothing smaller than 15 fits both conditions, and every other fit equals 8 plus some multiple of 15.
Why do the two moduli need to share no common factor?
Because that condition, coprimality, is exactly what guarantees a single solution exists at all. If both moduli shared a factor, certain remainder pairs would have no solution while others would have several below the product, and the clean one-answer guarantee this sheet depends on would fall apart.
How is this different from the Inverse Modulo page on this site?
That page returns one modular inverse and stops there; this page uses an inverse as an internal ingredient, not the final answer. Two remainder conditions go in, an inverse gets computed behind the scenes using the same Fermat's Little Theorem shortcut, and what comes out is the combined solution x — a different question with a differently shaped answer.
Is this the same calculation as the Fermat primality test on this site?
No. That page asks whether a single candidate is prime by checking one witness base, while this page never touches primality at all. It takes two remainder-and-modulus pairs and returns the number fitting both, borrowing only the inverse shortcut as a tool along the way, not as the point of the page.
Where does this theorem actually get used outside a classroom?
RSA decryption applies it to split one large exponentiation into two smaller ones, one per prime factor of the key, cutting real computing time. Scheduling puzzles use the identical structure: an event repeating every 3 days and another repeating every 5 line up on a shared date that this same two-congruence method pins down exactly.
Does a solution always exist for any two remainders and moduli?
Yes, provided the two moduli are coprime — sharing no common factor above 1. Whatever whole numbers r1 and r2 happen to be, some x below the product of the moduli satisfies both conditions, which is the guarantee that gives this theorem its name and its reliability across cryptography and scheduling alike.