Originally Posted by

**wsldam** I will prove when 'n' is an odd prime (so we can invoke Wilson's Theorem).

Let p be an odd prime. Then by Wilson's Theorem:

$\displaystyle -1 \equiv (p-1)! mod p$

$\displaystyle -1 \equiv 1 \cdot 2 \cdot ... \cdot \frac{p-1}{2} \cdot \frac{p+1}{2} \cdot ... \cdot (p-1) mod p$

Since $\displaystyle p \equiv 0 mod p$ we can freely subtract p from each term in the second half of the previous equation. This gives us:

$\displaystyle -1 \equiv 1 \cdot 2 \cdot ... \cdot \frac{p-1}{2} \cdot (-\frac{p-1}{2} \cdot ... \cdot (-1)) mod p$

Now note that in the second half of the right hand side there are $\displaystyle \frac{p-1}{2}$ '-1's' (pardon my notation abuse). Pulling out the '-1's' we have the result.

If $\displaystyle p \equiv 1 mod 4$ then $\displaystyle \frac{p-1}{2} \equiv 0 mod 2$. Hence, by our previous result, $\displaystyle -1 \equiv [(\frac{p-1}{2})!]^2 mod p$. Therefore $\displaystyle x^2 \equiv -1 mod p$ has a solution.