Number Theory: $x^2\equiv 1\pmod{140}$

Question

I have this problem assigned for homework and I'm confused as to how to solve an $x^2$ congruence. Here is the problem:

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

My only thought was to do something along the lines of:

$x^2\equiv 1\pmod{140}\implies x^2 -1= (x+1)(x-1)\equiv 0\pmod{140}\dotsc$

or to solve the system:

$x^2\equiv 1\pmod{2}, x^2\equiv 1\pmod{5}, x^2\equiv 1\pmod{7}$ since $140=2^2 \cdot 5 \cdot 7$.

And could I use the same techniques for solving this to also solve $x^2\equiv x\pmod{180}$?

Thanks in advance!

Answer 1

You get \begin{align} x^2 &= 1 \pmod 4\\ x^2 &= 1 \pmod 5 \\ x^2 &= 1 \pmod 7 \end{align}

The solution sets are \begin{align} x \in \{1,3\} \pmod 4 \\ x \in \{1,4\} \pmod 5 \\ x \in \{1,6\} \pmod 7 \end{align}

The CRT says the solution to \begin{align} x&=a \pmod 4 \\ x&=b \pmod 5 \\ x&=c \pmod 7 \end{align}

is $x=-35a+56b-20c \pmod{140}$

a     b     c       x
1     1     1       1
3     1     1     -69
1     4     1      29
3     4     1     -41
1     1     6      41
3     1     6     -29
1     4     6      69
3     4     6      -1