1. ## Problem (Wilson's)

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

2. Wilson's theorem states that $\displaystyle (p-1)!\equiv -1 \mod p$. Since $\displaystyle p-1 \equiv 0 \mod 4$ we can regroup the terms in the product $\displaystyle (p-1)!$ in pairs, as $\displaystyle [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
$\displaystyle (k!)^2\equiv-1 (mod p)$ where $\displaystyle k=\frac{p-1}{2}$ but can't quite see how to get to the required conclusion of $\displaystyle p\equiv1 (mod 4)$

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