 Solution

If $x^2\equiv -1(\mathrm{mod}p)$ with $p$ an odd prime, then $x^4\equiv 1$ but $x^2\not\equiv 1$. The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes $4\mid p-1$ necessary.

For sufficiency, suppose $p\equiv 1(\mathrm{mod}4)$ and put $r=(p-1)/2$, an even integer. Pair opposite factors in the factorial:Wilson's theorem gives $(r!{)}^2\equiv -1(\mathrm{mod}p)$, explicitly producing a square root of minus one modulo a prime. Thus