Chinese Remainder Theorem Calculator
The Chinese Remainder Theorem is one of the oldest results in number theory, and it answers a deceptively simple question: if you know what is left over when a hidden number is divided by several different divisors, can you recover the number itself? When those divisors share no common factors, the answer is yes, and there is exactly one such number between zero and the product of the divisors. This calculator takes three congruences, each written as a remainder and a modulus, and reconstructs the unique solution. It works by combining the congruences one at a time using modular inverses, the same constructive method taught in introductory number theory and used inside cryptographic libraries to speed up large computations. You supply the remainders and the moduli; the tool checks the logic and returns the smallest non-negative answer along with the product of the moduli, which is the period after which the pattern repeats. The result is computed deterministically from the standard formula shown below, never estimated, so the worked example reconciles exactly with the figures on screen. Use it to check homework, to verify a hand calculation, or to understand how splitting one large problem into smaller coprime pieces makes modular arithmetic faster and more reliable in practice.
The Chinese Remainder Theorem finds the unique x with x mod m_i equal to each remainder, where x = (sum of r_i x M_i x inverse) mod M. For x equal to 2 (mod 3), 3 (mod 5) and 2 (mod 7), the solution is x = 23 modulo 105.
Chinese Remainder Theorem formula
x = ( sum of r_i x M_i x y_i ) mod M
M = m_1 x m_2 x m_3 (product of the moduli)
M_i = M / m_i
y_i = inverse of M_i modulo m_i
r_i = remainder for modulus m_i
For each congruence we remove its own modulus from the product to get M_i, find the inverse of M_i so that M_i times y_i leaves remainder one modulo m_i, and weight each remainder by that term. Summing and reducing modulo M gives the one answer that satisfies every congruence at once. This requires the moduli to be pairwise coprime.
Worked example
Find x where x leaves remainder 2 modulo 3, remainder 3 modulo 5, and remainder 2 modulo 7.
- M = 3 x 5 x 7 = 105
- M_1 = 105 / 3 = 35, and 35 mod 3 = 2, so y_1 = 2 (since 2 x 2 = 4 = 1 mod 3)
- M_2 = 105 / 5 = 21, and 21 mod 5 = 1, so y_2 = 1
- M_3 = 105 / 7 = 15, and 15 mod 7 = 1, so y_3 = 1
- x = (2 x 35 x 2) + (3 x 21 x 1) + (2 x 15 x 1) = 140 + 63 + 30 = 233
- x = 233 mod 105 = 23
The unique solution is 23, and you can check it: 23 = 7 x 3 + 2, 23 = 4 x 5 + 3, and 23 = 3 x 7 + 2. These are the calculator's default inputs, so the result above matches the widget exactly.
Chinese Remainder Theorem calculator: frequently asked questions
What is the Chinese Remainder Theorem?
The Chinese Remainder Theorem states that if you know the remainders of an unknown integer when divided by several pairwise coprime moduli, there is exactly one solution between zero and the product of those moduli. It lets you reconstruct a single number from a set of independent congruences, which is why it appears throughout number theory, cryptography and computer arithmetic.
What does pairwise coprime mean?
Pairwise coprime means every pair of moduli shares no common factor other than one. For example 3, 5 and 7 are pairwise coprime, but 4 and 6 are not because they share the factor 2. The theorem guarantees a unique solution only when the moduli are pairwise coprime; otherwise a solution may not exist or may not be unique.
How is the solution computed?
Let M be the product of all moduli. For each congruence we form M_i = M divided by the modulus m_i, find the inverse of M_i modulo m_i, and add remainder times M_i times that inverse. Summing these terms and reducing modulo M gives the unique answer. This calculator performs every step deterministically.
What if no solution exists?
If the moduli are not pairwise coprime, the system can be inconsistent and have no solution, or it can have a solution modulo the least common multiple rather than the product. This tool assumes pairwise coprime moduli, the case the classical theorem covers, so always check that your moduli share no common factors.
Where is the Chinese Remainder Theorem used?
It speeds up large-integer arithmetic in cryptography (notably RSA decryption), supports error-correcting codes, and underlies many fast modular algorithms. By splitting one large computation into several small independent ones and recombining the results, it makes otherwise slow calculations practical.
Official sources
- Number theory and modular arithmetic reference: US National Institute of Standards and Technology (NIST). As at 25 June 2026.
Reviewed by the CalculatorHub team, edited by James Graham, 25 June 2026. See our methodology. This is general information, not financial, tax, legal or investment advice.