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$
 A: 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. 
A: The Legendre symbol sutisfies:
$$\left(\frac{-1}{p}\right) 
= (-1)^\tfrac{p-1}{2}
=\begin{cases}
\;\;\,1\mbox{ if }p \equiv 1\pmod{4} \\
-1\mbox{ if }p \equiv 3\pmod{4}  \end{cases}.$$
Thus for $p\equiv 1 \pmod4, \ \left(\frac{-1}{p}\right)=1$ and the result follows. 
Also see this.
