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?

Hint: Let $p = 2k + 1$. Consider $ x^{p-1} \pmod{p}$.     
Can you conclude that $k$ must be even? 

 We are given that $ x^2 \equiv -1 \pmod{p}$, so $ 1 \equiv x^{p-1} \equiv (-1)^{k} \pmod{p}$. 

