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

Question

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!

Answer 1

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.