6
$\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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ Chinese remainder theorem only lets you factor into prime power factors, not necessarily prime factors themselves. $\endgroup$ – W. Cadegan-Schlieper Oct 13 '15 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 '15 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 '15 at 1:38
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
|cite|improve this answer
$\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.