Chinese Remainder Theorem Calculator

Inputs

Enter at least two congruences. You may add up to eight more.

Congruence 1

a_{1}

Any integer.

n_{1}

Integer ≥ 2.

Congruence 2

a_{2}

Any integer.

n_{2}

Integer ≥ 2.

Try

Result

—

System of 3 congruences

$x \equiv 23 \pmod{105}$

\begin{cases}x \equiv 2 \pmod 3\\ x \equiv 3 \pmod 5\\ x \equiv 2 \pmod 7\end{cases}

Modulus $N$: 105; product of the moduli
Congruences: 3
Folds: 2

Pairwise combination steps

—

Fold	Folding in	$g=\gcd(n,n_i)$	Inverse used	Combined result

Each fold combines the running solution $x \equiv a \pmod n$ with the next congruence $x \equiv a_i \pmod{n_i}$ , using the inverse of $n$ mod $n_i$ (not the other way around) to find the new residue mod $n \cdot n_i$ . When $g=\gcd(n,n_i)>1$ the two congruences must agree modulo $g$ (otherwise there is no solution); the inverse is then that of $n/g$ mod $n_i/g$ , and the new modulus is $\operatorname{lcm}(n,n_i)=n\cdot n_i/g$ . A dash means $n_i$ already divides $n$ , so that congruence adds nothing new.