4
$\begingroup$

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!

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

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – MathQuestion Oct 14 '15 at 0:15
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Oct 14 '15 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.