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.]
Suppose $\displaystyle p|(x^2+1)$ for some $\displaystyle x\in \mathbb{Z}$ then $\displaystyle p|(x^4-1)$ since $\displaystyle x^4-1 = (x^2-1)\cdot (x^2+1)$ thus: if $\displaystyle o = \text{ord}_p(x)$ then $\displaystyle o|4$, but $\displaystyle o\not | 2$ since $\displaystyle x^2\equiv{-1}(\bmod.p)$ thus $\displaystyle o=4$.
By Fermat's Little Theorem: $\displaystyle x^{p-1}\equiv{1}(\bmod.p)$ and hence $\displaystyle o|(p-1)$ i.e. $\displaystyle p\equiv{1}(\bmod.4)$.
So there can be no solutions when $\displaystyle p\equiv{3}(\bmod.4)$.
Suppose $\displaystyle p\equiv{1}(\bmod.4)$, then $\displaystyle (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 $\displaystyle (p-1)!\equiv{-1}(\bmod.p)$, and since $\displaystyle p\equiv{1}(\bmod.4)$ we have $\displaystyle (-1)^{\frac{p-1}{2}} = 1$, thus $\displaystyle \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 $\displaystyle x^2\equiv{-1}(\bmod.p)$ follows easily from the fact that if you have $\displaystyle x^2\equiv{y^2}(\bmod.p)$ then either $\displaystyle x\equiv_p y$ or $\displaystyle 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.