1. ## Prove that.....

Let p be an odd prime. Prove that the congruence x2 is congruent to -1 mod p has no solutions for p is congruent to 3 mod 4 and exactly two solutions when p is congruent to 1 mod 4. [Hint: Think of orders.]

2. Suppose $p|(x^2+1)$ for some $x\in \mathbb{Z}$ then $p|(x^4-1)$ since $x^4-1 = (x^2-1)\cdot (x^2+1)$ thus: if $o = \text{ord}_p(x)$ then $o|4$, but $o\not | 2$ since $x^2\equiv{-1}(\bmod.p)$ thus $o=4$.

By Fermat's Little Theorem: $x^{p-1}\equiv{1}(\bmod.p)$ and hence $o|(p-1)$ i.e. $p\equiv{1}(\bmod.4)$.

So there can be no solutions when $p\equiv{3}(\bmod.4)$.

Suppose $p\equiv{1}(\bmod.4)$, then $(p-1)!=(p-1)...\cdot \left(p - \frac{p-1}{2}\right)\cdot \left(\frac{p-1}{2}\right) ... 1 \equiv{(-1)^{\frac{p-1}{2}}\left(\left(\tfrac{p-1}{2}\right) ... 1\right)^2}(\bmod.p)$

Now, by Wilson's Theorem $(p-1)!\equiv{-1}(\bmod.p)$, and since $p\equiv{1}(\bmod.4)$ we have $(-1)^{\frac{p-1}{2}} = 1$, thus $\left(\left(\tfrac{p-1}{2}\right) ... 1\right)^2\equiv{-1}(\bmod.p)$ and a solution exists.

The fact that there are exactly 2 solutions to $x^2\equiv{-1}(\bmod.p)$ follows easily from the fact that if you have $x^2\equiv{y^2}(\bmod.p)$ then either $x\equiv_p y$ or $x\equiv_p -y$

- I suppose you have not gone over quadratics residues, just as a comment this will get much more generalised when you get there.