2
$\begingroup$

I'd like to be able to determine when there exist square roots, in this case,$\pmod {67}$ and when square roots exist, how to compute them.

$x^2 \equiv 2 \pmod {67}$ and $x^2 \equiv 6 \pmod {67}$.

For the first one, I checked numbers squared up to $30$ and found no answers. For the second, I found that $26^2 \equiv 6 \pmod {67}$.

But this method is very time consuming and I can't say that $x^2 \equiv 2 \pmod {67}$ has no solutions, only that it has no solutions between $1$ and $30$.

$\endgroup$
2
$\begingroup$

Determining whether square roots exist modulo a prime and finding them is a big topic in elementary number theory. For example, there is a theorem that $x^2\equiv2\pmod p$ is soluble for a prime $p$ if and only if $p\equiv\pm1\pmod 8$. Beyond this you need to study quadratic reciprocity. Once you have quadratic reciprocity it is very quick to determine if you have a solution.

Finding a solution is a bit more difficult. Actually $67\equiv-1\pmod 4$ is an easier case. Suppose $p\equiv-1\pmod 4$. Then if $x^2\equiv a\pmod p$ is soluble then $a^{(p-1)/2}\equiv1\pmod p$ (this is Euler's Criterion). But in this case $(p+1)/2$ is even and we can take $x=a^{(p+1)/4}$ for then $$x^2=a^{(p+1)/2}=aa^{(p-1)/2}\equiv a\pmod p.$$ For $p\equiv1\pmod 4$ one needs more sophisticated approaches like the Tonelli-Shanks algorithm.

For square roots modulo a non-prime $n$ one can use the Chinese Remainder Theorem, provided one can factor $n$ into primes.

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