$x^{2} \equiv-1\ \pmod p$ has a solution if and only if $p\equiv 1\ \pmod 4$

Question

If $p$ is a prime. Then $x^{2} \equiv-1\ \pmod p$ has a solution if and only if $p\equiv 1\ \pmod 4$. Please explain in the easiest way.

Answer 1

I assume you mean odd primes.

If $$p \equiv 1 \pmod 4 \Rightarrow \left(\left(\frac{p-1}{2}\right)!\right)^2 \equiv -1 \pmod p (\because \text{Wilson's Theorem})$$ So we have shown that if $p \equiv 1 \pmod 4$, $x^2 \equiv -1 \pmod p$ exists.

Now let us show that if $x^2 \equiv -1 \pmod p$, then $p \equiv 1 \pmod 4$. If $$x^2 \equiv -1 \pmod p \Rightarrow (x^2)^{\frac{p-1}{2}} \equiv (-1)^{\frac{p-1}{2}} \equiv 1 \pmod p $$ By Fermat's Little Theorem.

Thus we have $\frac{p-1}{2} \equiv 0 \pmod 2$, and $p \equiv 1 \pmod 4$.

Answer 2

Here is a simple proof using group theory and the fact that $U(p)$ is cyclic. Assume $p$ is odd.

$x^{2} \equiv-1 \bmod p$ has a solution if and only if $U(p)$ has an element of order $4$.

Since $U(p)$ is a cyclic group, this happens iff $4$ divides the order of $U(p)$, which is $p-1$.