1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.