7
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Chinese remainder theorem only lets you factor into prime power factors, not necessarily prime factors themselves. $\endgroup$
    – W. Cadegan-Schlieper
    Oct 13, 2015 at 1:08
  • $\begingroup$ Almost. It should be $x^2\equiv 1\pmod{4}$. And yes, the same idea can be used for $x^2-x$. $\endgroup$
    – André Nicolas
    Oct 13, 2015 at 1:09
  • $\begingroup$ 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. $\endgroup$
    – GAVD
    Oct 13, 2015 at 1:38

1 Answer 1

Reset to default
1
$\begingroup$

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
$\endgroup$

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.