Chinese Remainder Theorem Calculator

The Chinese Remainder Theorem (CRT) says that if you have a system of congruences x = r1 (mod m1), x = r2 (mod m2), …, where all the moduli are pairwise coprime (no two share a common factor), then there is a unique solution modulo M = m1 * m2 * … * mk.

The theorem has been known in China since at least the 3rd century CE, appearing in the work of mathematician Sun Zi. It became widely studied in Europe after the 18th century and is now fundamental to number theory, cryptography, and computer science.

To solve the system, the algorithm works as follows:

1. Compute M = m1 * m2 * … * mk (product of all moduli).
2. For each i, compute Mi = M / mi.
3. Find yi such that Mi * yi is congruent to 1 (mod mi). This is the modular inverse of Mi modulo mi, computed via the Extended Euclidean Algorithm.
4. The solution is x = sum of (ri * Mi * yi) (mod M).

The modular inverse yi exists only because mi and Mi are coprime, which follows from the pairwise coprime assumption on the moduli.

A classic puzzle illustrating the theorem: “There is a number. When divided by 3 the remainder is 2. When divided by 5 the remainder is 3. When divided by 7 the remainder is 2. What is the smallest positive number?” The answer is 23. This calculator solves exactly this type of problem.

In cryptography, CRT is used to speed up RSA decryption. Instead of computing one large modular exponentiation, you compute two smaller ones and combine the results using CRT. This is typically four times faster.

In competitive programming, CRT appears whenever you need to combine information about remainders from different divisors, or when working modulo a product of distinct primes.