Let $p$ be a prime. Then prove that $x^2 \equiv -1\pmod p$ has solutions if and only if $p=2$ or $p\equiv 1\pmod 4$ 
Let $p$ be a prime. Then prove that $x^2 \equiv -1\pmod p$ has solutions if and only if $p=2$ or $p\equiv 1\pmod 4$.

Here is what is in my mind:
$x^2$ can be form of $4k+1$ or $4k$ , as there is involvement of modulus $4$. I think it is useful in some way. Now by Fermat's theorem we have 
$$x^{p-1} \equiv 1\pmod p$$
If $p=2$ then obviously has solutions.
I and not able to put together all these piece and form complete proof .Any suggestions
 A: Let $p$ be an odd prime. We have:
$$x^2 \equiv -1 \pmod{p} \implies (x^2)^{(p-1)/2} \equiv (-1)^{(p-1)/2} \pmod{p}$$
$$x^{p-1} \equiv (-1)^{(p-1)/2} \pmod{p}$$
By Fermat's Little Theorem, we have $x^{p-1} \equiv 1 \pmod{p}$ for $p \nmid x$. Thus:
$$(-1)^{(p-1)/2} \equiv 1 \pmod{p} \implies 2 \mid \frac{p-1}{2} \implies p \equiv 1 \pmod{4}$$
This solves the 'only if' case. Now, we are to show that $x^2 \equiv -1 \pmod{p}$ has solutions when $p \equiv 1 \pmod{4}$. We have:
$$(p-1)! \equiv \bigg(\prod_{i=1}^{(p-1)/2} i\bigg)\bigg(\prod_{i=1}^{(p-1)/2} (p-i)\bigg)\equiv\bigg(\prod_{i=1}^{(p-1)/2} i\bigg)\bigg(\prod_{i=1}^{(p-1)/2} (-i)\bigg) \pmod{p}$$
$$(p-1)! \equiv \bigg(\prod_{i=1}^{(p-1)/2} (i)\bigg)^2 \cdot (-1)^{(p-1)/2} \equiv \bigg(\prod_{i=1}^{(p-1)/2} (i)\bigg)^2 \pmod{p}$$
since $\frac{p-1}{2}$ is even. By Wilson's Theorem, $(p-1)! \equiv -1 \pmod{p}$. Thus, when $$x=\prod_{i=1}^{(p-1)/2} i$$ we have $x^2\equiv -1 \pmod{p}$ for $p \equiv 1 \pmod{4}$ which settles the 'if' case.
