# Number Theory: Chinese Remainder Theorem $x^2\equiv x\pmod{180}$

How can I use the Chinese Remainder Theorem to solve these two problems:

$x^2\equiv x\pmod{180}$

and

$x^2\equiv 1\pmod{140}$.

I was able to solve similar problems without using the Chinese Remainder Theorem, but I was wondering how to do these problems with the remainder theorem.

Thanks!

• Start by factoring the modulus into products of prime powers, for example. – hardmath Oct 14 '15 at 0:00

For the first problem, we want to solve $x(x-1)\equiv 0\pmod{2^23^25^1}$. This is equivalent to the system $$x(x-1)\equiv 0 \pmod{4};\quad x(x-1)\equiv 0\pmod{3};\quad x(x-1)\equiv 0\pmod{5}.$$

There are two solutions of the first congruence, namely $x\equiv 0\pmod{4}$ and $x\equiv 1\pmod{4}$.

Similarly, there are $2$ solutions of the second congruence, namely $x\equiv 0\pmod{9}$ and $x\equiv 1\pmod{9}$.

Similarly, there are two solutions of the third congruence.

For each of the $8$ combinations modulo prime powers, solve the resulting system of linear congruences using the CRT.

If you write down the general CRT solution of the system of congruences $x\equiv a\pmod{4}$, $x\equiv b\pmod{9}$, $x\equiv c\pmod{5}$, the $8$ solutions will not be difficult to calculate.

• Oh ok that makes sense, if I just calculate the general solution in terms of $a,b,c$ then I can just plug in the rest of the numbers for the 8 solutions. Thanks! – MathQuestion Oct 14 '15 at 0:15
• Yes, $0$ and $1$ in all combinations. For the congruence $x^2\equiv 1\pmod{140}$ (or anything else) we do something similar, except that the solutions come in $\pm$ pairs, half the work. One can do something similar with $x^2-x$ by completing the square, but there is not really a lot of time saved. – André Nicolas Oct 14 '15 at 0:22