Solution for quadratic congruence with $x^2 \equiv a \pmod p$

Question

The question is to find the solution of $x^2 \equiv 796$ in $\mathbb{Z}_{797}$.

I knew that we need to use the Euler criterion to check if the equation has a solution. Hence, I do know that this equation in $\mathbb{Z}_{797}$ does have a solution.

But how do I find the solution? I try to use the method $4k + 3$ and $8k + 5$ and it is not working.

Answer 1

We have $\left(\dfrac2{797}\right)=-1$ since $797\equiv5\mod8$, so $2^{398}\equiv-1\mod797,$

so a solution to $x^2\equiv-1\mod797$ is $x\equiv\pm2^{199}\mod797$.

$2^{199}=2^{128}2^{64}2^42^22^1.$ By repeated squaring,

$2^4=16, 2^8=256, 2^{16}\equiv182$, $2^{32}\equiv447, 2^{64}\equiv559$, and $2^{128}\equiv57\mod797$,

so $2^{199}\equiv57\times559\times128\equiv215\mod 797$.