Is there any solution to $x^2 \equiv 53 \mod97$ ( or in other words: is 53 quadratic residue of 97 ).
It is possible to place any of $0,1,...,96$ in the congruence and check if any of them is a solution, but there is got to be any easier way, which i can not think of. Would like to get some help or hints, Thank you!
$97$ is of the form $4n + 1$. Thus the quadratic residue in the 'prime clock' diagram is the same as a quadratic residue for $97 - 53 = 44$, which is $4 \times 11$. $4$ is a quadratic residue, and so is $11 = 37^2 = 1369 - 97 × 14$. Thus the answer is yes!
We have used a theorem which I will prove. By Fermat's Little Theorem, if $p$ is prime
$$\begin{align} k^2 - k \equiv 0 &{\bmod p} \\ k(k^{p -1} - 1) \equiv 0& {\bmod p} \\ k(k^{\frac{p-1}{2}} -1)(k^{\frac{p -1}{2}} + 1) \equiv 0& \bmod p. \end{align} $$ Thus since $k^{p -1} = (k^2)^{\frac{p - 1}{2}} $, this is a quadratic residue. Now for $p = 4n + 1$
$$(p - k)^{\frac{4n}{2}}k^{\frac{4n}{2}} \equiv 1 \bmod p$$ but for $p = 4n - 1$: $$(p - k)^{\frac{4n - 2}{2}}k^{\frac{4n - 2}{2}} \equiv -1 \bmod p$$