Suppose we have a prime \(p\) and \(x^2 ≡ -1 \bmod p\). If \(p=2\), then the solution would be trivial \((x = 1)\). Now let \(p ≡ 1 \bmod 4\). By Wilson's Theorem:
$$ (p - 1)! ≡ -1 \mod p $$
If we expand:
$$ (1)(2) \ldots \left( \frac{p-1}{2} \right) \left( \frac{p+1}{2} \right) \ldots(p-2)(p - 1) ≡ -1 \mod p $$
Since \(p - x ≡ -x \mod p\):
$$ (1)(2) \ldots \left( \frac{p-1}{2} \right) \left( \frac{p+1}{2} \right) \ldots(-2)(-1) ≡ -1 \mod p $$
Let's take the negative sign out:
$$ (1)(2) \ldots \left( \frac{p-1}{2} \right) \left( \frac{p-1}{2} \right) \ldots(2)(1) \times \left( (-1)^{\frac{p-1}{2}} \right) ≡ -1 \mod p $$
The second half is the same size as the first. If \(p=4k+1\), then \(\frac{p-1}{2} = 2k\), which means:
$$ \left ( (1)(2) \ldots \left( \frac{p-1}{2} \right) \right)^2 \times (1) ≡ -1 \mod p $$
Which means:
$$ \left ( \left( \frac{p-1}{2} \right) ! \right)^2 ≡ -1 \mod p $$
Thus, \(x^2 ≡ -1 \bmod p\) has the solution \(x = ((p - 1)/2)!\) when \(p ≡ 1 \bmod 4\).