−1 is a square modulo p if and only if p is not 3 modulo 4

Statement

Let $p$ be a prime number. There is an integer $x$ with $x^2 \equiv -1 \pmod p$ if and only if $p \not\equiv 3 \pmod 4$.

Remarks

For $p = 2$, take $x = 1$. For odd $p$, the statement is the first supplement to quadratic reciprocity. For $p \equiv 1 \pmod 4$, an explicit solution is $x = \left(\frac{p-1}{2}\right)!$, by Wilson's theorem. The statement is a step in the proof of Fermat's theorem on sums of two squares.

Explanations

L1 human

The primes $2$, $5$, $13$ and $17$ have a square root of $-1$: for example $5^2 = 25 \equiv -1 \pmod{13}$. The primes $3$, $7$ and $11$ have none. The rule is that $p$ must not leave remainder $3$ on division by $4$.