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
Solution 1:
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.