Chinese Remainder Theorem Calculator

Solve a system of three congruences x ≡ a (mod n) and find the unique solution x modulo the combined modulus N, using the standard Chinese Remainder Theorem construction for pairwise coprime moduli.

Quick Facts

Requirement
Moduli must be pairwise coprime
gcd(n⁢i, n⁢j) = 1 for every pair guarantees a unique solution modulo N = n₁×n₂×n₃.
Origin
Sunzi Suanjing, 3rd–5th century CE
The default 2/3, 3/5, 2/7 example is the classic remainder puzzle from that Chinese text.

Your Results

Calculated
Solution (x)
-
Smallest non-negative x satisfying all congruences
Combined modulus (N)
-
N = n₁ × n₂ × n₃
General solution
-
All solutions ≡ x (mod N)
Next solution
-
x + N, the following valid value

Ready

Enter three congruences (remainder and modulus) and press Calculate.

How the Chinese Remainder Theorem works

The Chinese Remainder Theorem (CRT) says that if you know the remainders an unknown integer x leaves when divided by several pairwise coprime moduli, those remainders together pin down x uniquely, modulo the product of the moduli. This calculator solves a system of three congruences of the form x ≡ a (mod n) and returns the smallest non-negative x that satisfies all of them at once.

The formula

Given x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), and x ≡ a₃ (mod n₃), where n₁, n₂, n₃ are pairwise coprime (gcd(n⁢i, n⁢j) = 1 for every pair), the classical construction builds the solution as follows:

  • Combined modulus: N = n₁ × n₂ × n₃
  • For each i, let N⁢i = N / n⁢i and let M⁢i be the modular inverse of N⁢i mod n⁢i (the value satisfying N⁢i × M⁢i ≡ 1 mod n⁢i, found with the extended Euclidean algorithm)
  • Solution: x = (a₁N₁M₁ + a₂N₂M₂ + a₃N₃M₃) mod N

The x this produces is the unique solution in the range 0 to N−1. Every other integer satisfying all three congruences differs from it by a multiple of N — that is, the full solution set is x, x + N, x + 2N, and so on (as well as x − N, x − 2N, ... in the negative direction).

Why the moduli must be coprime

The construction above only works when every pair of moduli shares no common factor. If two moduli share a factor greater than 1, a modular inverse may not exist and the "unique modulo N" guarantee breaks down — the system might have no solution at all, or the standard formula gives a wrong answer. This calculator checks gcd(n⁢i, n⁢j) for every pair before solving and flags the input if any pair is not coprime.

A worked example

The default values on this page — remainder 2 mod 3, remainder 3 mod 5, remainder 2 mod 7 — are the classic problem from the 3rd–5th century Chinese text Sunzi Suanjing. Here N = 3 × 5 × 7 = 105, and the unique solution is x = 23: check that 23 = 7×3 + 2, 23 = 4×5 + 3, and 23 = 3×7 + 2. Every number of the form 23 + 105k, such as 128 or −82, also satisfies all three congruences.

Applications

Beyond puzzle problems, the Chinese Remainder Theorem is a real computational tool. It speeds up modular exponentiation in RSA cryptography, where a private-key operation can be done separately modulo the two secret primes p and q, then recombined with CRT — several times faster than working modulo n = p×q directly. It also appears in scheduling problems with repeating cycles and in some checksum and error-correction schemes.

Frequently Asked Questions

What does x ≡ a (mod n) mean?
It means x and a leave the same remainder when divided by n, or equivalently that n divides (x − a) evenly. For example, x ≡ 2 (mod 3) means x leaves remainder 2 after division by 3, so x could be 2, 5, 8, 11, and so on.
Why must the moduli be pairwise coprime?
The standard Chinese Remainder Theorem guarantees a unique solution modulo N = n₁ × n₂ × n₃ only when every pair of moduli has a greatest common divisor of 1. If two moduli share a factor, the system may have no solution or the construction breaks down, so this calculator flags non-coprime moduli as invalid.
Is the solution x unique, or are there others?
The calculator returns the smallest non-negative solution x, along with the next one (x + N) to show the repeating pattern. Every valid solution is exactly x plus any integer multiple of N, positive or negative.
Where is the Chinese Remainder Theorem used in practice?
Beyond classic remainder puzzles, it speeds up modular exponentiation in RSA cryptography by computing separately modulo p and modulo q and then combining the results, and it underlies some scheduling and checksum problems involving repeating cycles.

Related calculators