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

Quote:

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

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

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

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

• Apr 11th 2009, 09:42 AM
mancillaj3
Quote:

Originally Posted by Soroban
Hello, mancillaj3!

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

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

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

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

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

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