Basic theory about divisibility and modular arithmetic

I am awfully bad with number theory so if one can provide a quick solution of this, it will be very much appreciated!

Prove that if $p$ is a prime with $p \equiv 1(\mod4)$ then there is an integer $m$ such that $p$ divides $m^2 +1$

Answer

I will assume that you know Wilson's Theorem, which says that if $p$ is prime, then $(p-1)!\equiv -1\pmod{p}$.

Let $m=\left(\frac{p-1}{2}\right)^2$. We show that if $p\equiv 1\pmod{4}$, then $m^2\equiv -1\pmod{p}$. This implies that $p$ divides $m^2+1$.

The idea is to pair $1$ with $p-1$, $2$ with $p-2$, $3$ with $p-3$, and so on until at the end we pair $\frac{p-1}{2}$ with $\frac{p+1}{2}$. To follow the argument, you may want to work with a specific prime, such as $p=13$. So we pair $1$ with $12$, $2$ with $11$, $3$ with $10$, $4$ with $9$, $5$ with $8$, and finally $6$ with $7$.

Thus for any $a$ from $1$ to $\frac{p-1}{2}$, we pair $a$ with $p-a$. Note that $a(p-a)\equiv -a^2\pmod{p}$.

So the product of all the numbers from $1$ to $p-1$ is congruent modulo $p$ to the product $$(-1^2)(-2^2)(-3^2)\cdot(-\left(\frac{p-1}{2}\right)^2).$$ This is congruent to $$(-1)^{\frac{p-1}{2}}m^2.$$ But $p-1$ is divisible by $4$, so $\frac{p-1}{2}$ is even, and therefore our product is congruent to $m^2$.

But our product is congruent to $(p-1)!$, and therefore, by Wilson's Theorem, it is congruent to $-1$.

We conclude that $m^2\equiv -1\pmod{p}$, which is what we wanted to show.