Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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.
