Prove that if $p$ is an odd prime such that $p\mid(x^2+1)$ for some $x\in\mathbb{Z}$, then $p\equiv 1 \pmod 4$ I've tried proving the statement using that $x^2\equiv -1\pmod p$, and someone told me that this actually just implies that $p\equiv 1\pmod 4$. But I don't see it. Can anyone help me with this problem?

$p | x^2+1$ it means $x^{2}  \equiv -1$ mod $p$. Taking the squares we have $x^4 \equiv 1$ mod $p$. 
We can re-think of $x$ as an element of $(\mathbb{Z}_{p})^{*}$ and the equation $x^{4}  \equiv 1$ mod $p$ tell us that $o(x) | p-1$, where $o(x)$ is of course the order of $x$.
Since $x^{2}  \equiv -1$ mod $p$ we notice that $x \ne [1]_{p}$ because it would have implied $x^{2} \equiv 1$ mod $p$, and for the same reason the order of $x$ can't be 2, otherwise powered to the square would have be the identity.
So the order of $x$ is exactly $4$, which give us $ 4 | p-1$, hence $p \equiv 1$ mod $4$
