Chinese Remainder Theorem
Solve systems of simultaneous congruences using the Chinese Remainder Theorem. Free online number theory calculator with step-by-step verification.
About This Calculator
The Chinese Remainder Theorem Calculator solves pairs of simultaneous linear congruences of the form x ≡ r1 (mod m1) and x ≡ r2 (mod m2), where the moduli m1 and m2 are coprime (gcd = 1). The theorem dates back to the 3rd-century Chinese mathematical text Sunzi Suanjing (Sun Tzu's Mathematical Classic) and was later formalized by Euler and Gauss.
To compute the solution, the calculator first checks that the moduli are coprime. It then computes the product M = m1 x m2 and, for each congruence, finds the modular inverse of M/mᵢ modulo mᵢ using the extended Euclidean algorithm. The final solution is x = (r1 x M2 x y1 + r2 x M1 x y2) mod M, where yᵢ is the modular inverse.
Example: Solve x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Here M = 15, M1 = 5, M2 = 3. The inverse of 5 mod 3 is 2, and of 3 mod 5 is 2. So x = (2 x 5 x 2 + 3 x 3 x 2) mod 15 = 38 mod 15 = 8. Verification: 8 mod 3 = 2 ✓, 8 mod 5 = 3 ✓.
Frequently Asked Questions
What is the Chinese Remainder Theorem?
The Chinese Remainder Theorem (CRT) states that if one knows the remainders of a number x when divided by pairwise coprime moduli, then x is uniquely determined modulo the product of those moduli. Formally, for congruences x ≡ r1 (mod m1) and x ≡ r2 (mod m2) with gcd(m1, m2) = 1, there is exactly one solution modulo M = m1 x m2.
How is the Chinese Remainder Theorem used in practice?
CRT is fundamental in cryptography (RSA decryption uses CRT to speed up computations), computer arithmetic (representing large integers via residues for efficient computation), error-correcting codes, and signal processing. It enables parallel computation by splitting a problem into smaller independent sub-problems.
What are coprime moduli and why do they matter?
Coprime (or relatively prime) moduli are integers whose greatest common divisor is 1. The Chinese Remainder Theorem requires the moduli to be pairwise coprime to guarantee a unique solution modulo their product. If the moduli share a common factor, the system may have no solution or multiple solutions.
How do you solve a system of congruence equations?
To solve x ≡ r1 (mod m1), x ≡ r2 (mod m2): (1) Compute M = m1 x m2. (2) For each congruence, compute Mᵢ = M ÷ mᵢ. (3) Find the modular inverse yᵢ of Mᵢ modulo mᵢ. (4) The solution is x = Sigma(rᵢ x Mᵢ x yᵢ) mod M. This calculator handles two congruences and shows the verification.
Can the CRT handle more than two congruences?
Yes, the Chinese Remainder Theorem generalizes to any number of congruences as long as the moduli are pairwise coprime. For n congruences, the same method applies: compute M = product of all moduli, then for each congruence find Mᵢ and its modular inverse. This calculator supports two congruences for clarity.
Does the Chinese Remainder Theorem apply to non-integer numbers?
The classical CRT applies only to integers and modular arithmetic with integer moduli. However, generalizations exist for polynomials, rings, and other algebraic structures where a similar decomposition is possible under the right conditions.