Chinese Remainder Theorem Calculator
Enter up to six congruences in the form x ≡ a (mod n) and the calculator instantly finds the unique smallest non-negative solution plus the general solution period. The step-by-step panel shows every stage of the extended Euclidean algorithm and the Bezout construction so you can follow (and check) the work at each line.
Formula
Worked example
A basket of sweets: divided among 3 children, 1 remains; among 4 children, 2 remain; among 5 children, 3 remain. System: x = 1 (mod 3), x = 2 (mod 4), x = 3 (mod 5). N = 60. M1 = 20, M2 = 15, M3 = 12. Inverses: 20*y1 = 1 (mod 3) gives y1 = 2; 15*y2 = 1 (mod 4) gives y2 = 3; 12*y3 = 1 (mod 5) gives y3 = 3. x = (1*20*2 + 2*15*3 + 3*12*3) mod 60 = (40 + 90 + 108) mod 60 = 238 mod 60 = 58. The basket held 58 sweets.
What is the Chinese Remainder Theorem?
The Chinese Remainder Theorem (CRT) is a fundamental result in number theory that guarantees a unique solution to a system of simultaneous modular congruences, provided the moduli are pairwise coprime. A congruence x = a (mod n) asks: what integers x leave remainder a when divided by n? When you have several such conditions at once, for example a number that leaves remainder 1 on division by 3, remainder 2 on division by 4, and remainder 3 on division by 5, the CRT tells you that a unique solution exists modulo the product of the moduli, and gives an explicit method to find it. The theorem dates to the 3rd-century text "Sun-tzu Suan-ching" and has applications in cryptography, computer arithmetic, signal processing, and competition mathematics.
How the algorithm works
The standard constructive proof of the CRT proceeds in four stages. First, compute N, the product of all moduli n1 through nk, and for each i compute Mi = N / ni. Second, for each pair (ni, Mi) use the extended Euclidean algorithm to find integers ui and vi satisfying Mi*ui + ni*vi = 1 (Bezout's identity), which is possible because gcd(Mi, ni) = 1 when all moduli are pairwise coprime. Third, the number ei = Mi * ui is the "idempotent" for equation i: it equals 1 modulo ni and 0 modulo every other nj. Fourth, form the weighted sum x = a1*e1 + a2*e2 + ... + ak*ek and reduce it modulo N. This calculator also handles the non-coprime case (generalised CRT) using an iterative pairwise combination, and reports when no solution exists. When moduli share common factors, a solution exists only if, for every pair i and j, the quantity (ai - aj) is divisible by gcd(ni, nj).
Bezout's identity and modular inverses
A key sub-problem is computing the modular inverse of Mi modulo ni: the integer yi such that Mi * yi = 1 (mod ni). This is found via the extended Euclidean algorithm, which runs the ordinary Euclidean GCD algorithm while tracking the linear combination at each step. Starting from gcd(Mi, ni) = 1, back-substitution yields the Bezout coefficients (ui, vi) with Mi*ui + ni*vi = 1, so Mi*ui = 1 (mod ni), giving yi = ui mod ni. The "Show your work" panel in this calculator displays each of these intermediate values so you can follow or replicate the calculation by hand.
Applications in cryptography and computing
The Chinese Remainder Theorem is used extensively in practical computing. In RSA cryptography, the CRT variant of decryption splits the large modular exponentiation into two smaller ones modulo the prime factors p and q, then reconstructs the result, cutting the time by roughly a factor of four. In computer hardware, CRT-based number systems allow arithmetic on large integers to be parallelised across several smaller processors, each working modulo a different prime. In the Number Field Sieve, the fastest known algorithm for factoring large integers, CRT is used to combine results across many small primes. Competition mathematics problems frequently disguise a linear congruence system as a puzzle, such as "find the smallest positive integer that leaves these remainders when divided by...", which CRT resolves in seconds.
Classic Chinese Remainder Theorem examples
| System of congruences | Smallest solution | Period |
|---|---|---|
| x ≡ 1 (mod 3), x ≡ 2 (mod 4), x ≡ 3 (mod 5) | 58 | 60 |
| x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) | 23 | 105 |
| x ≡ 0 (mod 3), x ≡ 1 (mod 4), x ≡ 2 (mod 5) | 57 | 60 |
| x ≡ 1 (mod 2), x ≡ 1 (mod 3), x ≡ 1 (mod 5) | 1 | 30 |
| x ≡ 3 (mod 5), x ≡ 5 (mod 7), x ≡ 7 (mod 11) | 838 | 385 |
| x ≡ 0 (mod 4), x ≡ 0 (mod 6) | 0 | 12 |
Well-known problems from number theory and competition mathematics solved by CRT.
Frequently asked questions
When does the Chinese Remainder Theorem have no solution?
When the moduli are NOT pairwise coprime, a solution may or may not exist. For each pair of congruences x = ai (mod ni) and x = aj (mod nj), a solution exists only when ai - aj is divisible by gcd(ni, nj). If this compatibility condition fails for any pair, the system is inconsistent and has no solution. This calculator checks every pair and reports an incompatibility if found.
Do the moduli have to be prime?
No. The classic theorem requires only that the moduli be pairwise coprime, meaning each pair shares no common factor other than 1. They do not need to be prime themselves. For example, moduli 4, 9, and 25 are pairwise coprime even though none is a prime. The generalised form (used here) also handles non-coprime moduli by checking the compatibility condition and using the LCM as the period rather than the full product.
What is "pairwise coprime" and why does it matter?
A set of integers is pairwise coprime when every pair of them has a greatest common divisor of 1. For example, the set {3, 4, 5} is pairwise coprime because gcd(3,4) = 1, gcd(3,5) = 1, and gcd(4,5) = 1. Pairwise coprimality is the condition that guarantees a unique solution modulo the product N = n1 * n2 * ... * nk. When it holds, the solution space has exactly N values in each full cycle: one in each period of length N.
How do I verify the solution?
Substitute the smallest solution x back into each congruence. For each i, compute x mod ni and check that the remainder equals ai. Because the construction is exact, a correct implementation always passes verification. The "Show your work" panel in this calculator includes a verification row for every congruence.
What does the period N mean in practice?
If x is one solution, then x + N, x + 2*N, x + 3*N, ... are also solutions, and so is x - N, x - 2*N, and so on. There are infinitely many solutions but they form a single arithmetic progression with common difference N. This calculator shows the smallest non-negative solution and the next one (x + N), so you can see the pattern immediately.
Can the remainder be larger than the modulus?
Remainders are always reduced modulo the modulus before solving. If you enter a remainder ai that is larger than ni, the calculator automatically reduces it to the equivalent value in the range [0, ni - 1] before computing. Negative remainders are similarly wrapped into the positive range.
What is the connection to modular arithmetic and RSA?
RSA encryption relies on modular exponentiation over a composite modulus n = p * q. During decryption, the CRT lets you split one hard exponentiation mod n into two much easier ones mod p and mod q (each roughly half the bit-length), then recombine with a single CRT step. This CRT-RSA optimisation reduces decryption time by a factor of roughly 4 without any change in security.