# 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}$?

• Chinese remainder theorem only lets you factor into prime power factors, not necessarily prime factors themselves. – W. Cadegan-Schlieper Oct 13 '15 at 1:08
• Almost. It should be $x^2\equiv 1\pmod{4}$. And yes, the same idea can be used for $x^2-x$. – André Nicolas Oct 13 '15 at 1:09
• Ater checking by a small codes, I got 8 solutions for $x^2 \equiv 1$ (mod 140): 1, 29, 41, 69, 71, 99, 111, 139. – GAVD Oct 13 '15 at 1:38

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