# Proof by contradiction Let $n \in \mathbb{N}$. Any odd prime factor $p$ of $n^2 +1$ has the form $p = 4k+1$ for some integer $k \geq 0$.

Let $n \in \mathbb{N}$. Any odd prime factor $p$ of $n^2 +1$ has the form $p = 4k+1$ for some integer $k \geq 0$.

Proof using contradiction. I am a little bit stuck, can someone help me get started on this question

• Have a look at math.stackexchange.com/questions/552398/… Nov 5, 2013 at 5:31
• That is quite different from this. Nov 5, 2013 at 5:33
• Assume there is a prime divisor $p = 4k + 3$ of $n^2 + 1$. Then by the result of the question I linked we have $n^{p-1} \equiv -1$ mod $p$. You should be able to derive a contradiction from that. Nov 5, 2013 at 5:34
• So, dude, you know what the Legendre symbol is? Nov 5, 2013 at 5:36
Hint: Suppose, towards a contradiction, that $p$ does not have the form $4k+1$, where $k \geq 0$. Then by the Division Algorithm, we know that for some $k \geq 0$, we have either $p=4k$ or $p=4k+2$ or $p=4k+3$. But it can't be $4k$ or $4k+2$, since $p$ is odd. So we may assume that $p=4k+3$ for some $k \geq 0$. Use this to get a contradiction.