If $x$ is even and $f(x)=x^2 + 1$ is indeed composite, are the prime divisors of $f(x)$ congruent to $1$ mod $4$?
Asked
Active
Viewed 1,289 times
4
-
1f(3) = 10 and 2 is a prime divisor of 10. – Emanuele Paolini Oct 10 '15 at 07:25
-
@jevie: What is this "oh I forgot..."? Why don't you edit it out, and make the question statement current now that you have remembered something. – P Vanchinathan Oct 10 '15 at 07:43
-
2The answer is yes. If you want a proof, it can be found in your typical elementary number theory textbook. Main relevant lemma: if $p\equiv3\pmod4$ and $p\mid(a^2+b^2)$, then $p\mid a$ and $p\mid b$. – Greg Martin Oct 10 '15 at 08:01
-
Do you know a link about the proof? – unknownMe Oct 10 '15 at 09:53
1 Answers
3
Let us assume $p$ is a prime divisor of $n^2 + 1$ for $n$ even. Clearly $p$ must be odd, and we want to show that $p \equiv 1 \pmod{4}$.
One "big hammer" approach is to use quadratic residues. Note that if $p$ divides $n^2 + 1$, then $n^2 \equiv -1 \pmod{p}$, so $-1$ is a quadratic residue mod $p$.
Euler's criterion says that $a$ is a quadratic residue mod prime $p$ exactly when:
$$ a^{\frac{p-1}{2}} \equiv 1 \pmod{p} $$
For the special case $a=-1$ this says $-1$ is a quadratic residue precisely when $(p-1)/2$ is even. That is, not only is $p$ an odd number, but $p-1$ is a multiple of four, i.e. $p \equiv 1 \pmod{4}$ as we wanted to show.
This special case was already known to Fermat, as described by this extended classroom note on quadratic reciprocity by Pete L. Clark.
