Math Help - Problem (Wilson's)

1. Problem (Wilson's)

Let p be an odd prime. Prove that the quadratic congruence $x^2+1 \equiv 0\pmod{p}$ has a solution if and only if $p \equiv1 \pmod{4}$. (hint: use Wilson's theorem)

2. Wilson's theorem states that $(p-1)!\equiv -1 \mod p$. Since $p-1 \equiv 0 \mod 4$ we can regroup the terms in the product $(p-1)!$ in pairs, as $[1\times(p-1)][2 \times (p-2)]\dots\left[\frac{p-1}{2}\times \frac{p-1}{2}\right] \equiv (-1^2)(-2^2)\dots\left(-\left(\frac{p-1}{2}\right)^2\right) \mod p$.

Can you take it from there?

3. Alright, I have the <= direction.

For the => direction, i have worked with wilson's down to
$(k!)^2\equiv-1 (mod p)$ where $k=\frac{p-1}{2}$ but can't quite see how to get to the required conclusion of $p\equiv1 (mod 4)$

4. Well if $a^d \equiv 1 \mod p$ and $a^j \not\equiv 1 \mod p$ for $1 \leq j < d$ then we always must have $d|p-1$. What can you say about the order of $x$ mod $p$ if $x^2\equiv -1 \mod p$?