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$

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.
