Chinese Remainder Theorem Calculator

It solves a system of simultaneous congruences x = a1 (mod n1), x = a2 (mod n2), and so on, when the moduli are pairwise coprime. It returns the unique solution x in the range 0 to N minus 1, where N is the product of all the moduli. Enter a residue and a modulus for each congruence, and the calculator works through the construction for you.

Pairwise coprime means every pair of moduli shares no common factor other than 1, so the greatest common divisor of any two moduli is 1. The Chinese Remainder Theorem guarantees a single unique solution mod N only under this condition. If two moduli share a factor (for example 4 and 6, which share 2), the calculator returns no solution because the theorem does not apply directly.

First it sets N equal to the product of all the moduli. For each congruence it computes Ni = N divided by ni, then finds Mi, the modular inverse of Ni mod ni, using the extended Euclidean algorithm. The solution is the sum of ai times Ni times Mi for every congruence, reduced mod N. This is the standard Gauss construction, the same method described in the ancient Sun Tzu text.

Yes. A residue like negative 1 is allowed and is normalized into the range 0 to n minus 1 before solving. For example, x = negative 1 (mod 3) is the same as x = 2 (mod 3). The calculator reduces each residue automatically, so you can enter whichever form is convenient.

The calculator keeps the combined modulus N within the exact integer range of standard arithmetic (up to 2 to the power of 53 minus 1) so every result is precise. It accepts up to 12 congruences, each modulus up to 1,000,000,000, and reduces large intermediate products with exact modular multiplication. If the product of your moduli would exceed the safe range, it returns no solution rather than an inexact one.

Take the solution x and compute x mod n for each modulus. Each result should equal the residue you entered (after reducing that residue into the 0 to n minus 1 range). The calculator shows a verification line confirming the share of congruences satisfied, which reads 100 percent when the solution is exact.