• April 10th 2009, 11:51 PM
mancillaj3
$x^{2} \cong -1(mod\ 122)$
• April 11th 2009, 04:13 AM
Soroban
Hello, mancillaj3!

Quote:

$x^2 \:\equiv\: -1 \!\! \pmod{122}$

Since $-1 \equiv 121 \!\!\pmod{122}$

. . we have: . $x^2 \:\equiv\:121\!\!\pmod{122}$

Therefore: . $x \:\equiv\:\pm11\!\!\pmod{122}$

• April 11th 2009, 10:42 AM
mancillaj3
Quote:

Originally Posted by Soroban
Hello, mancillaj3!

Since $-1 \equiv 121 \!\!\pmod{122}$

. . we have: . $x^2 \:\equiv\:121\!\!\pmod{122}$

Therefore: . $x \:\equiv\:\pm11\!\!\pmod{122}$

that means it has two solutions? but what about using legendre would it work $x^{2} \cong -1(mod\ 2*61)$
• April 11th 2009, 05:17 PM
ThePerfectHacker
Quote:

Originally Posted by mancillaj3
$x^{2} \cong -1(mod\ 122)$

You have $x^2\equiv 11^2(\bmod 122)$ therefore $x^2\equiv 11^2(\bmod 2)$ and $x^2\equiv 11^2(\bmod 61)$. Therefore, $x \equiv \pm 11 (\bmod 2)$ and $x\equiv \pm 11(\bmod 61)$. Now use Chinese remainder theorem to get solutions mod $122$.