Solving system...
Ready to solve the system
Enter 2–4 modular congruences with pairwise coprime moduli to find the unique solution with full Extended Euclidean working.
What Is the Chinese Remainder Theorem?
The Chinese Remainder Theorem (CRT) is one of the oldest results in number theory. It states that if you have a system of simultaneous modular congruences — equations of the form x ≡ rᵢ (mod mᵢ) — and all the moduli m₁, m₂, …, mₙ are pairwise coprime (any two share no common factor), then the system has a unique solution modulo M, where M is the product of all the moduli.
The theorem originates from Sun Tzu's Mathematical Classic (3rd–5th century CE), which posed the problem: "There is an unknown number of things. Counted in threes, the remainder is 2. Counted in fives, the remainder is 3. Counted in sevens, the remainder is 2. How many things are there?" The answer is 23 — the smallest positive integer satisfying all three conditions simultaneously.
Beyond its historical charm, CRT is a workhorse in modern computing. RSA decryption, hash table design, error-correcting codes, and calendar scheduling all rely on it.
How the Chinese Remainder Theorem Algorithm Works
The standard CRT construction builds a solution by summing independent contributions, one per congruence. Each contribution uses a modular inverse found via the Extended Euclidean Algorithm.
Worked example — Sun Tzu's problem: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7):
M = 3 × 5 × 7 = 105 M₁ = 105/3 = 35 ; 35 mod 3 = 2 ; inv(2, 3) = 2 ; term₁ = 2 × 35 × 2 = 140 M₂ = 105/5 = 21 ; 21 mod 5 = 1 ; inv(1, 5) = 1 ; term₂ = 3 × 21 × 1 = 63 M₃ = 105/7 = 15 ; 15 mod 7 = 1 ; inv(1, 7) = 1 ; term₃ = 2 × 15 × 1 = 30 x = (140 + 63 + 30) mod 105 = 233 mod 105 = 23 Check: 23 mod 3 = 2 ✓ 23 mod 5 = 3 ✓ 23 mod 7 = 2 ✓
What Does "Pairwise Coprime" Mean?
Two integers are coprime (also called relatively prime) if their greatest common divisor is 1. In a CRT system, all moduli must be pairwise coprime — meaning every pair of moduli is coprime, not just adjacent ones. For a three-modulus system (m₁, m₂, m₃), that requires gcd(m₁, m₂) = 1, gcd(m₁, m₃) = 1, and gcd(m₂, m₃) = 1 simultaneously.
For example, 3, 5, and 7 are pairwise coprime: gcd(3,5) = gcd(3,7) = gcd(5,7) = 1. But 4 and 6 are not coprime (gcd = 2), so the pair (4, 6) cannot be used in a standard CRT system. This calculator checks every pair automatically and reports the first failing pair if one exists.
Coprimality is necessary because the Extended Euclidean Algorithm must find a modular inverse of Mᵢ mod mᵢ. That inverse exists if and only if gcd(Mᵢ, mᵢ) = 1 — which holds exactly when mᵢ is coprime to every other modulus.
Understanding Modular Inverses in CRT
The heart of the CRT algorithm is finding yᵢ, the modular inverse of Mᵢ mod mᵢ. A modular inverse of a mod m is an integer y such that a × y ≡ 1 (mod m). It exists when gcd(a, m) = 1.
The Extended Euclidean Algorithm finds this inverse efficiently. Rather than guessing, it works backwards through the Euclidean division steps to express 1 as a linear combination of a and m. The coefficient of a in that expression is the inverse.
Mᵢ × yᵢ ≡ 1 (mod mᵢ)
This guarantees the contribution rᵢ × Mᵢ × yᵢ ≡ rᵢ (mod mᵢ) and ≡ 0 (mod mⱼ) for all j ≠ i
Applications of the Chinese Remainder Theorem
RSA Cryptography
CRT speeds up RSA private-key operations by splitting one computation over a large modulus n = p×q into two smaller computations over p and q, then combining with CRT. This gives a roughly 4× speed-up in decryption.
Scheduling & Calendars
CRT finds when periodic events coincide. If event A repeats every 3 days and event B repeats every 5 days, and today A has 2 days left and B has 3 days left, CRT gives the exact day they next align — no brute-force needed.
Error-Correcting Codes
Redundant Number Systems (RNS) represent integers by their remainders under several coprime moduli. CRT reconstructs the original number from the residues, enabling fault-tolerant computation where individual channels can fail without losing the value.
Competitive Mathematics
CRT is a standard olympiad technique. Problems asking "for which n does n leave remainder 2 when divided by 3, remainder 1 when divided by 4, and remainder 5 when divided by 7?" are solved directly with this calculator.
Chinese Remainder Theorem FAQ
What is the Chinese Remainder Theorem?
The Chinese Remainder Theorem states that a system of congruences x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂), …, x ≡ rₙ (mod mₙ) has a unique solution modulo M = m₁ × m₂ × … × mₙ, provided all moduli are pairwise coprime. The theorem guarantees both existence and uniqueness of the solution.
Why must the moduli be pairwise coprime?
Pairwise coprimality ensures the modular inverse of Mᵢ = M/mᵢ with respect to mᵢ exists. It also guarantees that the contributions rᵢ × Mᵢ × yᵢ from each congruence do not interfere with each other — contribution i evaluates to rᵢ mod mᵢ and to 0 mod mⱼ for every j ≠ i.
What happens if the moduli are not coprime?
If two moduli share a common factor, the standard CRT construction fails because the required modular inverse does not exist. Solutions may still exist (via Garner's algorithm or careful analysis), but they are not guaranteed and the uniqueness property is lost. This calculator reports an error when moduli are not pairwise coprime.
How do I find the modular inverse used in CRT?
The modular inverse of Mᵢ mod mᵢ is found using the Extended Euclidean Algorithm. First reduce Mᵢ mod mᵢ to a smaller integer aᵢ, then run the extended GCD on (aᵢ, mᵢ). The algorithm expresses gcd(aᵢ, mᵢ) = 1 as a linear combination of aᵢ and mᵢ; the coefficient of aᵢ, taken modulo mᵢ, is the inverse. This calculator shows every division step.
Can the CRT solve more than two congruences?
Yes — the standard CRT works for any number of pairwise coprime congruences. The algorithm simply sums one contribution per congruence. This calculator supports up to 4 congruences and shows the working for each one individually.
What is the general form of the CRT solution?
The unique solution in [0, M) is the minimal non-negative x satisfying all congruences simultaneously. The complete solution set is all integers of the form x + k×M for any integer k, written as x ≡ solution (mod M).
How is CRT used in RSA encryption?
In RSA, the private key involves two large primes p and q, with public modulus n = p×q. Decrypting a message m raised to the private exponent d requires computing mᵈ mod n — an expensive operation for large n. CRT speeds this up: compute mᵈ mod p and mᵈ mod q separately (both much faster), then combine with CRT to get mᵈ mod n. Since p and q are prime (and therefore coprime), CRT applies directly.
What is Sun Tzu's original problem?
Sun Tzu Suan Ching (Master Sun's Mathematical Manual, 3rd–5th century CE) poses: "We have things of unknown number. Counted in threes, the remainder is 2. Counted in fives, the remainder is 3. Counted in sevens, the remainder is 2. How many things are there?" In modern notation: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). The answer is 23. Try it in the calculator above.
Related Calculators
GCD & Extended Euclidean Calculator
Full algorithm steps, Bezout coefficients, and modular inverse
Modular Arithmetic Calculator
Add, subtract, multiply, and divide in modular arithmetic
Euler's Totient Calculator
Count integers coprime to n with prime factorisation steps
Prime Factorization Calculator
Factor any integer into its prime components with a tree diagram
GCF & LCM Calculator
Greatest common factor and least common multiple for multiple numbers
Factorial Calculator
Compute n! with step-by-step multiplication breakdown