Chinese Remainder Theorem Calculator

Background.

Some time between the third and fifth centuries, a Chinese arithmetic manual, the Sunzi Suanjing, posed a puzzle that has outlived almost everything else in it. There is an unknown number of things. Counted in threes, two are left over; counted in fives, three are left over; counted in sevens, two are left over. How many things are there? The smallest answer is 23, and the general method behind it is now called the Chinese remainder theorem.

Its claim is that remainders on division by moduli sharing no common factor pin a whole number down completely within a cycle as long as the product of those moduli. Remainder 2 on division by 3 and remainder 3 on division by 5 leave exactly one candidate between 0 and 14, the number 8, and every other solution is 8 plus a multiple of 15.

The page solves that two-congruence case, x ≡ a (mod m) and x ≡ b (mod n), returning the least non-negative solution and the combined modulus m × n. Puzzles with three or more conditions, Sunzi's included, are handled by chaining: solve one pair, then pair the answer and its combined modulus with the next condition.

The no-common-factor condition is not a technicality. The traditional Chinese calendar names years by pairing ten heavenly stems with twelve earthly branches, and because 10 and 12 both divide by 2, the pairs repeat after 60 years rather than 120; half of the possible combinations never occur. Moduli like that produce either no solution or one that repeats sooner than m × n, and the page declines them rather than guess.

The same arithmetic runs inside modern cryptography. RSA implementations commonly use it to split one large modular computation into two smaller ones, one for each secret prime, and then recombine the results.

What is chinese remainder theorem calculator?

The Chinese remainder theorem states that when two moduli m and n are coprime, meaning their greatest common divisor is 1, the pair of congruences x ≡ a (mod m) and x ≡ b (mod n) has exactly one solution between 0 and m × n − 1, and every other solution differs from it by a multiple of m × n. The remainders a and b lie between 0 and one less than their moduli. The theorem extends to any number of moduli, provided every pair of them is coprime.

How to use this calculator.

1. 01Enter the first remainder a and its modulus m: for 'leaves 2 when divided by 3', a is 2 and m is 3. Use whole numbers only, and reduce a remainder that is too large first, so 17 mod 5 goes in as 2.
2. 02Enter the second remainder b and modulus n in the same way.
3. 03Make sure the moduli share no factor. 8 and 9 are fine even though neither is prime; 6 and 9 both divide by 3, and the page will refuse them.
4. 04For three or more conditions, solve the first two, then enter that solution as a new remainder and the combined modulus as its modulus alongside the next condition.
5. 05Read the least non-negative solution, and add or subtract the combined modulus to list the others.

The formula.

Every number meeting the first condition can be written x = a + m·k for some whole number k, so the task is to choose k so that the second condition holds as well. That requires m·k ≡ b − a (mod n). Because m and n are coprime, m has an inverse modulo n: a number m⁻¹ with m·m⁻¹ ≡ 1 (mod n), which the page finds with the extended Euclidean algorithm. Multiplying through gives k = (b − a)·m⁻¹ mod n, and then x = (a + m·k) mod (m·n). The final reduction puts the answer between 0 and m·n − 1. If m and n share a factor, m has no inverse modulo n and this construction breaks down, which is why the page checks gcd(m, n) = 1 before anything else. The arithmetic is exact integer arithmetic, and the page refuses moduli whose product reaches 10^15, the point at which it would have to print the answer in rounded scientific notation.

A worked example.

Frequently asked questions.

References& sources.

1. [1]NIST Digital Library of Mathematical Functions, section 27.14, Chinese Remainder Theorem.
2. [2]OpenStax, Contemporary Mathematics, modular arithmetic.
3. [3]BIPM, The International System of Units (SI Brochure), 9th ed., version 3.01, coherent derived units and quantity equations.