<s>[INST] Number Theory: $x^2\equiv 1\pmod{140}$ 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!
 [/INST] 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

</s>