If a prime divides an integer of the form $n^2+1$ then ... This question is from my problem set  in number theory. I tried it a week ago and again today but both times I couldn't solve it.
Problem: If a prime p divides an integer of the form $n^2+1$ , then $p\not\equiv 3 \pmod{4}$.
I thought of attempting this problem by assuming $p\equiv 3\pmod{4} $.  But I am unable to move towards anything concrete.
Can you please give some hints?
Thanks!
 A: You're right on assuming that $p\equiv 3\pmod{4}$ and then trying arrive at a contradiction. Here's how it may work out.
Suppose that $p\equiv 3\pmod{4}$ and $p$ divides $n^2+1.$ If $p$ divides $n^2+1,$ then we have;
$$n^2+1\equiv 0\pmod{p}$$
$$n^2\equiv -1\pmod{p}.$$
Now, since we have assumed that $p\equiv 3\pmod{4}$ we know that $p=4k+3$ for some positive $k.$ Thus, we have;
\begin{align*}
n^{p}
&\equiv n^{4k+3}\pmod{p}\\
&\equiv n\left(n^{4k+2}\right)\pmod{p}\\
&\equiv n\left(n^2\right)^{2k+1}\pmod{p}.
\end{align*}
Note that $n^2\equiv -1\pmod{p},$ so we have;
\begin{align*}
n^{p}
&\equiv n\left(n^2\right)^{2k+1}\pmod{p}\\
&\equiv n\left(-1\right)^{2k+1}\pmod{p}\\
&\equiv n(-1)\pmod{p}\\
&\equiv -n\pmod{p}.
\end{align*}
But by the Fermat's Little Theorem, we have $n^p\equiv n\pmod{p}.$ So we have $n\equiv -n\pmod{p},$ which simplifies to $p\mid 2n.$ However, we can see that this is incorrect as $p$ also divides $n^2+1$ which is coprime to $2n$. So we have finally arrived a contradiction and your claim is proven.
