Prime Divisors of $x^2 + 1$

Question

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$?

Answer 1

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.