Chinese Remainder Theorem Calculator
Free Chinese remainder theorem Calculator for arithmetic. Enter values to get step-by-step solutions with formulas and graphs.
Formula
x = sum(ai * Mi * yi) mod M, where M = product of all mi
For a system of congruences x = ai (mod mi), compute M = product of all moduli, Mi = M/mi, yi = modular inverse of Mi mod mi. The unique solution modulo M is the sum of ai * Mi * yi, reduced modulo M.
Worked Examples
Example 1: Classic Sun Tzu Problem
Problem: Find a number that gives remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7.
Solution: M = 3 x 5 x 7 = 105\nM1 = 105/3 = 35, inverse of 35 mod 3: 35 x 2 = 70, 70 mod 3 = 1, so y1 = 2\nM2 = 105/5 = 21, inverse of 21 mod 5: 21 x 1 = 21, 21 mod 5 = 1, so y2 = 1\nM3 = 105/7 = 15, inverse of 15 mod 7: 15 x 1 = 15, 15 mod 7 = 1, so y3 = 1\nx = (2 x 35 x 2) + (3 x 21 x 1) + (2 x 15 x 1) = 140 + 63 + 30 = 233\n233 mod 105 = 23
Result: x = 23 (general solution: x = 23 + 105k for any integer k)
Example 2: Four-Congruence System
Problem: Solve: x = 1 (mod 2), x = 2 (mod 3), x = 3 (mod 5), x = 4 (mod 7).
Solution: M = 2 x 3 x 5 x 7 = 210\nM1=105, y1=1; M2=70, y2=1; M3=42, y3=3; M4=30, y4=4\nx = (1x105x1) + (2x70x1) + (3x42x3) + (4x30x4)\nx = 105 + 140 + 378 + 480 = 1103\n1103 mod 210 = 53\nVerify: 53 mod 2=1, 53 mod 3=2, 53 mod 5=3, 53 mod 7=4. All correct.
Result: x = 53 (general solution: x = 53 + 210k for any integer k)
Frequently Asked Questions
What is the Chinese Remainder Theorem?
The Chinese Remainder Theorem (CRT) is a fundamental result in number theory that provides a way to solve a system of simultaneous congruences with pairwise coprime moduli. It states that if the moduli are pairwise coprime, then there exists a unique solution modulo the product of all the moduli. The theorem dates back to the 3rd century Chinese mathematician Sun Tzu, who posed a problem about finding a number that leaves specific remainders when divided by 3, 5, and 7. The CRT has profound implications in modern mathematics and computer science, forming the basis for many algorithms in cryptography, coding theory, and computational number theory.
What are the applications of the Chinese Remainder Theorem in cryptography?
The CRT is extensively used in modern cryptography, particularly in the RSA encryption system. RSA decryption can be performed approximately four times faster using CRT by splitting the computation into two smaller modular exponentiations instead of one large one. This optimization, known as CRT-RSA, is standard in virtually all practical RSA implementations. CRT is also used in secret sharing schemes where a secret is split among multiple parties such that a minimum number must cooperate to reconstruct it. Additionally, CRT appears in homomorphic encryption schemes, threshold cryptography, and the generation of large prime numbers used in cryptographic key generation.
What is the historical origin of the Chinese Remainder Theorem?
The Chinese Remainder Theorem originated in the 3rd century CE with the Chinese mathematician Sun Tzu (not the military strategist), who posed the problem in his work Sunzi Suanjing. The original problem asked for a number that gives remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7, with the answer being 23. Indian mathematician Aryabhata also discovered similar results independently around 499 CE. The theorem was later formalized by European mathematicians including Euler and Gauss in the 18th and 19th centuries. Gauss included a version in his landmark work Disquisitiones Arithmeticae. The modern abstract algebraic formulation generalizes CRT to rings and ideals.
Can the Chinese Remainder Theorem handle more than three congruences?
Yes, the Chinese Remainder Theorem works for any finite number of simultaneous congruences, as long as all the moduli are pairwise coprime. The algorithm generalizes naturally: compute M as the product of all moduli, find Mi and modular inverses for each congruence, and sum the products. With k congruences, the solution is unique modulo M = m1 * m2 * ... * mk. In practice, for very large systems, it can be more efficient to solve pairs of congruences iteratively rather than computing the full product at once. This iterative approach combines two congruences at a time into a single equivalent congruence, reducing the system step by step until only one congruence remains.
How do I get the most accurate result?
Enter values as precisely as possible using the correct units for each field. Check that you have selected the right unit (e.g. kilograms vs pounds, meters vs feet) before calculating. Rounding inputs early can reduce output precision.
Is Chinese Remainder Theorem Calculator free to use?
Yes, completely free with no sign-up required. All calculators on NovaCalculator are free to use without registration, subscription, or payment.