How to find a solution to $x^2 \equiv 7 \pmod{787}$

Question

Find a solution to $x^2 \equiv 7 \pmod{787}$.

The answer should be between $1$ and $786$ but beyond that I don't know how to do it.

Answer 1

"Find a solution to $x^2 \equiv 7 \pmod{787}$"

Here's the solution. We have two solutions, given your constraints, $x=105$ and $x=682$.

$$105^2=11025=3^2 \cdot 5^2 \cdot 7^2 \equiv 7\mod 787$$ $$682^2=2^2 \cdot 11^2 \cdot 31^2 \equiv 7 \mod 787$$

These can be proved to be the only solutions by using proof by exhaustion. If you want a derivation use this answer. In general, this is the Tonelli-Shanks algorithm. Please read up on that and then come back.

We have $p=787$ and $n=7$. We also have $7^{(787-1)/{2}} \equiv 1$. Now we see that,

$$787-1=786=393 \cdot 2=393 \cdot 2^1=Q \cdot 2^S$$

We have $Q=393$ and $S=1$ so we are done. The solution is given by,

$$7^{(787+1)/4} \mod 787=7^{197} \mod 787=105$$

Which can be solved using the Carmichael function and friends. After that,

The other solution is therefore $787-105$. So the solutions are $x=105$ and $x=682$.

Answer 2

Note that I am working in $\mathbb{Z}_{p}$ where $p$ is a prime (i.e. the elements are equivalence classes, so that I don't need to use (mod $p$)).

As easily follows from Fermat's little theorem $a^p= a$ for all $a$ in $\mathbb{Z}_p$. It follows that if $p +1$ is divisible by $4$, and $x^2 = a$, then $( a^{\frac{p+1}{4}})^2 = ((x^2)^{\frac{p+1}{4}})^2= x^{4 \frac{p+1}{4}}=x^{p+1}=x^2=a$. This tells us that if $a$ has square roots they can be computed as $\pm a^{\frac{p+1}{4}}$.

In your example we compute $x=[7]^{197}=[105]$ and the other one as $-x = [682]$.