numvana

Chinese Remainder Theorem Calculator

Solve a pair of simultaneous congruences x ≡ a₁ (mod n₁) and x ≡ a₂ (mod n₂) for the smallest matching integer.

Smallest solution (x)
8
Combined modulus
15
General solution
x = 8 + 15k, for any integer k

How it works

The Chinese Remainder Theorem answers: what's the smallest whole number x that leaves remainder a₁ when divided by n₁, and remainder a₂ when divided by n₂? When n₁ and n₂ are coprime (share no common factor), a solution always exists and is unique modulo n₁×n₂ — this calculator finds it with the extended Euclidean algorithm rather than by trial and error, which is what makes it practical even for large moduli.

It also handles the more general case where n₁ and n₂ aren't coprime: let g = gcd(n₁, n₂). A solution exists only if a₁ and a₂ agree modulo g (they must, since any x satisfying both congruences leaves the same remainder mod g either way); when one exists, it's unique modulo lcm(n₁, n₂) instead of the simple product.

The 'general solution' shown — x = (smallest solution) + (combined modulus)×k for any integer k — captures every number satisfying both congruences at once, since adding a full cycle of the combined modulus never changes either remainder.

FAQ

What if there's no solution?

That happens only when the moduli share a common factor g and the two remainders disagree modulo g — for example x ≡ 0 (mod 4) forces x even while x ≡ 1 (mod 6) forces x odd, which can never both hold. The calculator detects this and explains why, rather than returning a wrong number.

Can this solve three or more congruences at once?

Not directly — this calculator is scoped to exactly two congruences. You can still chain it: solve the first two, then treat that combined result (its solution and its combined modulus) as a new single congruence to combine with a third.

What's this actually used for?

Beyond its classical role in number theory, it's the basis of RSA's CRT optimization (decrypting faster by working modulo each of the two secret primes separately and recombining) and shows up in scheduling problems phrased as 'find a day that's a Tuesday and also the 3rd of some 5-day cycle' — the same two-congruence shape as this calculator.

Related calculators