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≡2(mod3), x≡3(mod5), x≡2(mod7)x \equiv 2 \pmod{3},\ x \equiv 3 \pmod{5},\ x \equiv 2 \pmod{7}

x≡23(mod105)\displaystyle x \equiv 23 \pmod{105}

Smallest non-negative solution

23\displaystyle 23

General solution

x=23+105k\displaystyle x = 23 + 105k

Combined modulus

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

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

    x≡2(mod3),  x≡3(mod5),  x≡2(mod7)x \equiv 2 \pmod{3},\ \ x \equiv 3 \pmod{5},\ \ x \equiv 2 \pmod{7}
  2. Combining two congruences

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

    2+3t≡3(mod5)⇒t≡2(mod5)⇒x≡8(mod15)\begin{gathered} 2 + 3t \equiv 3 \pmod{5} \\ \Rightarrow \\ t \equiv 2 \pmod{5} \\ \Rightarrow \\ x \equiv 8 \pmod{15} \end{gathered}
  3. Combining with the congruence mod 7

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

    8+15t≡2(mod7)⇒t≡1(mod7)⇒x≡23(mod105)\begin{gathered} 8 + 15t \equiv 2 \pmod{7} \\ \Rightarrow \\ t \equiv 1 \pmod{7} \\ \Rightarrow \\ x \equiv 23 \pmod{105} \end{gathered}
  4. Checking every congruence

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

    23 mod 3=2,  23 mod 5=3,  23 mod 7=223 \bmod 3 = 2,\ \ 23 \bmod 5 = 3,\ \ 23 \bmod 7 = 2
  5. Result

    So x≡23(mod105)x \equiv 23 \pmod{105}: every x=23+105kx = 23 + 105k works.

Worked examples