Consider the quadratic congruence $x^2 + 1 \equiv 0 \pmod p$ where $p$ is prime.
Prove that $x^2 + 1 \equiv 0 \pmod p$ has a solution if and only if $p= 2$ or $p \equiv 1 \pmod 4$.
We need to prove both directions.
($\impliedby$)
There are two cases, $p= 2$ and $p \equiv 1 \pmod 4$.
In the case $p=2$, the congruence is $x^2 +1 \equiv 0 \pmod 2$. This is equivalent to $x^2 \equiv -1 \equiv 1 \pmod 2$. This has a solution, which is $x \equiv 1 \pmod 2$.
In the case $p \equiv 1 \pmod 4$, we have $p = 1 + 4k$ for some integer $k$. This gives $\frac{p-1}{2}=2k$, and even number, which we'll use below.
Before we proceed, we derive a result from Wilson's Theorem.
$$ \begin{align} -1 & \equiv (p-1)! \\ \\ & \equiv 1 \times 2 \times \ldots \frac{p-1}{2} \times \frac{p+1}{2} \ldots \times (p-2) \times (p-1) \pmod p \\ \\ & \equiv \underbrace{1 \times 2 \times \ldots \frac{p-1}{2}}_{\frac{p-1}{2} \text{ multiplicands}} \times \underbrace{ \left ( -\frac{p-1}{2} \right ) \ldots \times (-2) \times (-1)}_{\frac{p-1}{2} \text{ multiplicands}} \pmod p \\ \\ & \equiv (-1)^{\frac{p-1}{2}}\left ( (\frac{p-1}{2})! \right ) ^2 \pmod p \\ \\ & \equiv (-1)^{2k}\left ( (\frac{p-1}{2})! \right )^2 \pmod p \\ \\ & \equiv \left ( (\frac{p-1}{2})! \right )^2 \pmod p \end{align} $$
This gives us a solution to $x^2 \equiv -1 \pmod p$, namely $x \equiv (\frac{p-1}{2})! \pmod p$.
We have shown that in both cases, $p= 2$ and $p \equiv 1 \pmod 4$, the congruence $x^2 \equiv -1 \pmod p$ has a solution.
($\implies$)
The prime $p$ conforms to one of three cases, $p=2$, $p \equiv 1 \pmod 4$ and $p \equiv 3 \pmod 4$. If we show that the final case $p=3 \equiv \pmod 4$ is not possible, then one of the remaining two cases must hold.
For the purpose of contradiction, we assume $p \equiv 3 \pmod 4$, that is, $p=3+4k$ for some integer $k$.
Since the prime $p$ does not divide $x$, we can use the FlT. If $p$ did divide $x$ then $x^2 +1 \equiv 0 +1 \equiv 1 \pmod p$ which contradicts the given congruence.
$$ \begin{align} 1 & \equiv x^{p-1} \pmod p \\ \\ & \equiv x^{2+4k} \pmod p \\ \\ &\equiv (x^2) \times (x^2)^{2k} \pmod p \\ \\ & \equiv (-1) \times (1) \pmod p \\ \\ 1 & \equiv -1 \pmod p \end{align}$$
This is a contradiction, so the case $p \equiv 3 \pmod 4$ is not possible.
This leaves us with the desired conclusion that $p= 2$ or $p \equiv 1 \pmod 4$.
We have shown both directions, $\implies$ and $\impliedby$, and so we conclude the bidirectional implication, $x^2 + 1 \equiv 0 \pmod p$ has a solution if and only if $p= 2$ or $p \equiv 1 \pmod 4$.