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$
$\endgroup$
5
-
$\begingroup$ Have a look at math.stackexchange.com/questions/552398/… $\endgroup$– ArthurNov 5, 2013 at 5:31
-
$\begingroup$ That is quite different from this. $\endgroup$– albertNov 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$– ArthurNov 5, 2013 at 5:34
-
$\begingroup$ So, dude, you know what the Legendre symbol is? $\endgroup$– Will JagyNov 5, 2013 at 5:36
-
$\begingroup$ this question is already asked and answer is in the comments... math.stackexchange.com/questions/549783/… $\endgroup$– user87543Nov 5, 2013 at 6:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
