x^2 ≡ -1 mod p is solvable if and only if p = 2 or p ≡ 1 mod 4

Suppose we have a prime \(p\), if we take modulo 4, then there are four possibilities, \((1 \mod 4)\), \((2 \mod 4)\), \((3 \mod 4)\) and \((4 \mod 4)\). Since \(p\) is even only when 2, then \(p\) cannot be \((2 \mod 4)\) or \((4 \mod 4)\) except when 2. To prove \(x^2 ≡ -1 \mod p\) is solvable if and only if \(p = 2\) or \(p ≡ 1 \mod 4\), we just need to show that there is no solution when:

$$ p ≡ 3 \mod 4 $$

If \(p ≡ 3 \mod 4\), then \(p = 4k + 3\), which would also mean:

$$ p - 1 = 4k + 2 = 2(2k + 1) $$

Since \(x^2 ≡ -1 \mod p\):

$$ (x^2)^{(2k + 1)} ≡ (-1)^{(2k + 1)} ≡ -1 \mod p $$

but also:

$$ x^{(4k + 2)} ≡ x^{(p-1)} ≡ 1 \mod p $$

So \(1 ≡ -1 \mod p\), that's possible when \(p=2\), but not when \(p=3 \mod 4\). If \(p ≡ 1 \mod 4\), then \(p = 4k + 1\) for some positive integer k. Thus, \((p - 1)/2\) is even. 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 (-1)^l ≡ -1 \mod p $$

The second half is the same size as the first and they are both even, so \(l\) is even:

$$ \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 \mod p\) has the solution \(x = ((p - 1)/2)!\) when \(p ≡ 1 \mod 4\).

Suppose we have a prime \(p\), if we take modulo 4, then there are four possibilities, \((1 \mod 4)\), \((2 \mod 4)\), \((3 \mod 4)\) and \((4 \mod 4)\). Since \(p\) is even only when 2, then \(p\) cannot be \((2 \mod 4)\) or \((4 \mod 4)\) except when 2. To prove \(x^2 ≡ -1 \mod p\) is solvable if and only if \(p = 2\) or \(p ≡ 1 \mod 4\), we just need to show that there is no solution when: