Chinese Remainder Theorem Calculator
Free Chinese remainder theorem Calculator for arithmetic. Enter values to get step-by-step solutions with formulas and graphs.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Chinese Remainder Theorem Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: x = sum(ai * Mi * yi) mod M, where M = product of all mi
Worked example — x = 23 (general solution: x = 23 + 105k for any integer k)
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 M1 = 105/3 = 35, inverse of 35 mod 3: 35 x 2 = 70, 70 mod 3 = 1, so y1 = 2 M2 = 105/5 = 21, inverse of 21 mod 5: 21 x 1 = 21, 21 mod 5 = 1, so y2 = 1 M3 = 105/7 = 15, inverse of 15 mod 7: 15 x 1 = 15, 15 mod 7 = 1, so y3 = 1 x = (2 x 35 x 2) + (3 x 21 x 1) + (2 x 15 x 1) = 140 + 63 + 30 = 233 233 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 M1=105, y1=1; M2=70, y2=1; M3=42, y3=3; M4=30, y4=4 x = (1x105x1) + (2x70x1) + (3x42x3) + (4x30x4) x = 105 + 140 + 378 + 480 = 1103 1103 mod 210 = 53 Verify: 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 does pairwise coprime mean and why is it required?
Two numbers are coprime (or relatively prime) if their greatest common divisor is 1, meaning they share no common factors other than 1. Pairwise coprime means that every pair of numbers in the set must be coprime with each other. For example, the set {3, 5, 7} is pairwise coprime because gcd(3,5)=1, gcd(3,7)=1, and gcd(5,7)=1. This condition is necessary for the standard CRT to guarantee a unique solution modulo the product of all moduli. Without pairwise coprimality, the system may have no solution or multiple solutions within the range. A generalized version of CRT exists for non-coprime moduli, but it requires additional compatibility conditions on the remainders.
How does the CRT algorithm work step by step?
The CRT algorithm follows a systematic process to find the unique solution. First, compute M, the product of all moduli. For each congruence, compute Mi = M divided by the current modulus. Then find the modular multiplicative inverse yi of Mi modulo the current modulus using the extended Euclidean algorithm. Multiply the remainder by Mi and yi to get each term. Sum all terms and take the result modulo M to get the smallest non-negative solution. The solution satisfies all congruences simultaneously, and the general solution is x = solution + k*M for any integer k. This constructive proof directly gives us the algorithm used in Chinese Remainder Theorem Calculator.
What is the extended Euclidean algorithm used in CRT?
The extended Euclidean algorithm is an extension of the standard Euclidean algorithm that not only computes the greatest common divisor of two integers a and b, but also finds integers x and y such that ax + by = gcd(a,b). This is crucial for CRT because we need to find the modular multiplicative inverse of Mi modulo each modulus. When gcd(Mi, modulus) = 1 (which is guaranteed by the pairwise coprime condition), the coefficient x gives us the modular inverse. The algorithm works recursively by applying the division algorithm and back-substituting to express the GCD as a linear combination. It runs in O(log(min(a,b))) time, making it very efficient for practical computations.
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.
How is CRT used in computer science beyond cryptography?
Beyond cryptography, the Chinese Remainder Theorem has numerous applications in computer science. In parallel computing, CRT allows large integer arithmetic to be decomposed into independent smaller computations on each residue, which can be processed simultaneously. In error-correcting codes, CRT-based redundancy helps detect and correct data corruption in storage and transmission systems. Database systems use CRT-inspired techniques for hash-based partitioning of data across multiple servers. In computer algebra systems, CRT reconstructs polynomial coefficients from evaluations at multiple points. Signal processing uses CRT in connection with the discrete Fourier transform and number-theoretic transforms for fast multiplication.
What happens when the moduli are not pairwise coprime?
When the moduli are not pairwise coprime, the standard CRT does not directly apply, but a generalized version can sometimes provide a solution. The system of congruences x = a1 (mod m1) and x = a2 (mod m2) has a solution if and only if a1 is congruent to a2 modulo gcd(m1, m2). If this compatibility condition is met, the solution is unique modulo lcm(m1, m2) rather than modulo m1*m2. When the condition is not met, no solution exists. For practical computation with non-coprime moduli, one approach is to factor each modulus into prime powers and apply CRT to the prime power components, checking compatibility at each step.
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.
How do you verify a CRT solution is correct?
Verifying a CRT solution is straightforward and much simpler than finding the solution itself. For each congruence in the system, divide the solution by the corresponding modulus and check that the remainder matches the specified remainder. For example, if the solution is 23 for the system x=2 (mod 3), x=3 (mod 5), x=2 (mod 7), verify: 23 mod 3 = 2 (correct), 23 mod 5 = 3 (correct), 23 mod 7 = 2 (correct). Additionally, verify that the solution is the smallest non-negative value by confirming it is less than the product of all moduli (M = 3*5*7 = 105). The general solution set is then 23, 128, 233, and so on, each differing by exactly M = 105.
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.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
📐Pythagorean Theorem
Calculate hypotenuse of right triangles
🧮Triangle Inequality Theorem Calculator
Calculate triangle inequality theorem with inputs, formulas, and instant results.
🧮Fermats Little Theorem Calculator
Calculate fermats little theorem with inputs, formulas, and instant results.
🧮Remainder Calculator
Calculate remainder with inputs, formulas, and instant results.
🧮Mean Value Theorem Calculator
Calculate mean value theorem with inputs, formulas, and instant results.
🧮Bayes Theorem Calculator
Calculate bayes theorem with inputs, formulas, and instant results.
🧮Binomial Expansion Calculator
Expand binomial expressions using the binomial theorem with Pascal triangle coefficients.
🧮Bayesian Probability Calculator
Calculate posterior probability using Bayes theorem from prior, likelihood, and evidence.