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

  • $\begingroup$ Have a look at math.stackexchange.com/questions/552398/… $\endgroup$
    – Arthur
    Nov 5, 2013 at 5:31
  • $\begingroup$ That is quite different from this. $\endgroup$
    – albert
    Nov 5, 2013 at 5:33
  • $\begingroup$ 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. $\endgroup$
    – Arthur
    Nov 5, 2013 at 5:34
  • $\begingroup$ So, dude, you know what the Legendre symbol is? $\endgroup$
    – Will Jagy
    Nov 5, 2013 at 5:36
  • $\begingroup$ this question is already asked and answer is in the comments... math.stackexchange.com/questions/549783/… $\endgroup$
    – user87543
    Nov 5, 2013 at 6:22

1 Answer 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .