Chinese remainder theorem calculator

How it works

A system $x \equiv r_1 \pmod{m_1}, \dots, x \equiv r_k \pmod{m_k}$ asks for a number with given remainders. The classic puzzle: a number leaves $2$ when divided by $3$, $3$ by $5$ and $2$ by $7$; the answer is $23$, and every $23 + 105 j$.

When the moduli are pairwise coprime, the Chinese remainder theorem says there is exactly one solution modulo $M = m_1 \cdots m_k$, and Gauss’s formula builds it: with $M_i = M / m_i$ and $y_i \equiv M_i^{-1} \pmod{m_i}$, the sum $x = \sum r_i M_i y_i$ works, since each term is $r_i$ modulo its own $m_i$ and $0$ modulo all the others.

When moduli share factors, merge the congruences one at a time: put $x = r_1 + m_1 k$ into the next one, solve the linear congruence for $k$, and get a single congruence modulo $\operatorname{lcm}(m_1, m_2)$. This fails exactly when two remainders disagree modulo the gcd of their moduli (as $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 6$ do modulo 2). RSA uses the theorem to decrypt about four times faster, by working modulo $p$ and $q$ separately.