# Computing modular square roots

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

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.