Chinese Remainder Theorem Calculator

Enter the remainders and the moduli, each separated by commas.

The remainders a, separated by commas.

The moduli m, separated by commas, each 2 or more.

Try

Result

You enteredx≡1(mod4), x≡3(mod6)x \equiv 1 \pmod{4},\ x \equiv 3 \pmod{6}

x≡9(mod12)\displaystyle x \equiv 9 \pmod{12}

Smallest non-negative solution

9\displaystyle 9

General solution

x=9+12k\displaystyle x = 9 + 12k

Combined modulus

12\displaystyle 12
Show the work
  1. The system of congruences

    Find the numbers xx that satisfy all 22 congruences at once. When the moduli share factors, the congruences are combined two at a time and checked for compatibility.

    x≡1(mod4),  x≡3(mod6)x \equiv 1 \pmod{4},\ \ x \equiv 3 \pmod{6}
  2. Combining two congruences

    Write x=1+4tx = 1 + 4t so that the first congruence holds, then choose the whole number tt that makes the second hold too. The new modulus is lcm⁡(4,6)=12\operatorname{lcm}(4, 6) = 12.

    1+4t≡3(mod6)⇒t≡2(mod3)⇒x≡9(mod12)\begin{gathered} 1 + 4t \equiv 3 \pmod{6} \\ \Rightarrow \\ t \equiv 2 \pmod{3} \\ \Rightarrow \\ x \equiv 9 \pmod{12} \end{gathered}
  3. Checking every congruence

    Dividing the answer by each modulus should leave the stated remainder.

    9 mod 4=1,  9 mod 6=39 \bmod 4 = 1,\ \ 9 \bmod 6 = 3
  4. Result

    So x≡9(mod12)x \equiv 9 \pmod{12}: every x=9+12kx = 9 + 12k works.

Worked examples