Chinese Remainder Theorem Calculator
The Chinese Remainder Theorem finds the unique integer x (in a range 0 to M-1, where M is the product of all moduli) that simultaneously satisfies a system of congruences: x is congruent to a1 mod m1, x is congruent to a2 mod m2, and x is congruent to a3 mod m3. Enter up to three pairs of (remainder, modulus). Optionally leave the third pair blank to solve a two-congruence system. All moduli must be pairwise coprime (every pair has gcd = 1). The algorithm computes Mi = M/mi for each congruence, finds the modular inverse of Mi modulo mi using the extended Euclidean algorithm, and combines the terms as x = sum of (ai times Mi times Mi_inverse) mod M. The theorem was known to the Chinese mathematician Sunzi around the 3rd to 5th century AD and was fully proved by Qin Jiushao in 1247. Modern applications include RSA cryptography, digital signal processing, and modular arithmetic on computers.
CRT algorithm
Given x ≡ a1 (mod m1), x ≡ a2 (mod m2), ...
M = m1 * m2 * ... (product of all moduli)
For each i: Mi = M / mi
For each i: yi = Mi^(-1) mod mi (modular inverse)
x = (a1*M1*y1 + a2*M2*y2 + ...) mod M
Requires: all pairs of moduli pairwise coprime
CRT: frequently asked questions
What is the Chinese Remainder Theorem?
The Chinese Remainder Theorem (CRT) states that if the moduli m1, m2, ..., mk are pairwise coprime (every pair shares gcd = 1), then for any choice of remainders a1, a2, ..., ak, there exists a unique integer x in [0, m1*m2*...*mk) that satisfies all congruences x ≡ a1 (mod m1), x ≡ a2 (mod m2), etc. simultaneously.
Why must the moduli be pairwise coprime?
Pairwise coprimality ensures the system has a unique solution. If two moduli share a common factor d greater than 1, the system may have no solution (if the corresponding remainders are inconsistent modulo d) or infinitely many solutions modulo the LCM (if consistent). The CRT requires strict pairwise coprimality for the uniqueness guarantee.
How does the CRT algorithm work?
The standard CRT construction: let M = m1*m2*...*mk (the total modulus). For each i, compute Mi = M/mi, then find yi = Mi^(-1) mod mi (the modular inverse of Mi modulo mi). The solution is x = sum of ai*Mi*yi, taken modulo M. This calculator follows this construction exactly.
What is a real-world use of the CRT?
The CRT is used in RSA decryption to speed up computation by working modulo p and q separately (where n=p*q) and then combining. It also appears in computing large-number arithmetic, scheduling problems with periodic events, and the construction of error-correcting codes.
What happens if the moduli are not pairwise coprime?
This calculator checks all pairs (gcd of each pair of moduli) and reports an error if any pair is not coprime. In that case, the CRT in its standard form does not apply. A generalised CRT exists for non-coprime moduli, but this calculator uses only the standard version.
Sources
- CRT in number theory: Wolfram MathWorld, Chinese Remainder Theorem.
- CRT in RSA: NIST SP 800-56B Rev. 2.
Reviewed by the CalculatorHub team, edited by James Graham, 14 June 2026. See our methodology.