Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 1 / 1H / Solution

For an odd prime $p$, the Legendre symbol $(a/p)$ is $0$ if $p\mid a$, $1$ if $a$ is a nonzero square modulo $p$, and $-1$ otherwise. Euler's criterion statesIf $p\mid a$ both sides vanish. Otherwise write $a\equiv g^j$ for a primitive root $g$. The squares are precisely the even powers of $g$, while $g^{(p-1)/2}$ has order two and therefore equals $-1$. Hence $a^{(p-1)/2}=(-1{)}^j$, proving the criterion and the useful special case $(-1/p)=(-1{)}^{(p-1)/2}$.

For odd $n$, $n^2+4\equiv 5(\mathrm{mod}8)$. Every prime divisor $p$ of this number is odd, and $p\nmid n$, so $(n/2{)}^2\equiv -1(\mathrm{mod}p)$. Euler's criterion forces $p\equiv 1(\mathrm{mod}4)$, hence $p\equiv 1$ or $5(\mathrm{mod}8)$. A product of such primes can be $5(\mathrm{mod}8)$ only if a prime $5(\mathrm{mod}8)$ occurs to an odd power.

Suppose the primes $5(\mathrm{mod}8)$ were $p_1,\dots ,p_r$. Choose the odd integer $n=p_1\cdots p_r$ (or $n=1$ for an empty list). None of these primes divides $n^2+4$, since the latter is $4$ modulo each $p_i$. Yet the preceding argument gives a prime divisor $5(\mathrm{mod}8)$, outside the list. This contradiction proves infinitely many primes congruent to $5$ modulo $8$.