Past exam of the options II course of the University of Oxford / 2009 / C / C2

For an odd prime number $p$, the Legendre symbol $(a/p)$ is zero if $p\mid a$, is $+1$ if $a$ is a nonzero square modulo $p$, and is $-1$ otherwise.

Euler criterion states thatWhen $p\nmid a$, the power is congruent to $+1$ or $-1$, according as $a$ is or is not a quadratic residue.

Gauss lemma for quadratic residues states: for $p\nmid a$, take the least positive residues of $a,2a,\dots ,((p-1)/2)a$ modulo $p$, and let $s$ be the number greater than $p/2$. Then

For $a=2$, the least positive residues in Gauss lemma for quadratic residues are simply $2,4,\dots ,p-1$. The number exceeding $p/2$ isFor $p\equiv 1,3,5,7(\mathrm{mod}8)$, respectively, this count is even, odd, odd, even. Substituting these parities into the lemma gives

By multiplicativity of the Legendre symbol and Euler criterion,Combining this with part (iv) yields

Suppose all primes congruent to $3$ modulo eight are $p_1,\dots ,p_r$, and put $N=p_1\cdots p_r$, an odd integer. The integer $N^2+2$ is odd and congruent to three modulo eight. If a prime $q$ divides it, then $N^2\equiv -2(\mathrm{mod}q)$ and $q\nmid N$, since a common divisor of $N$ and $N^2+2$ would divide two. Thus $(-2/q)=1$, so part (v) forces $q\equiv 1$ or $3(\mathrm{mod}8)$.

If all prime factors congruent to three had even multiplicity, their product, including the factors congruent to one, would be one modulo eight. Since $N^2+2$ is three modulo eight, at least one prime factor is congruent to three and occurs to odd multiplicity. But it is none of the $p_i$, since those divide $N$. This contradiction proves infinitely many primes are congruent to three modulo eight.