Past exam of the Probability, statistics and options II course of the University of Oxford / 2009 / C / C2

For an odd prime $p$, the Legendre symbol is $\boxed{(a/p)=0}$ if $p\mid a$, $\boxed{(a/p)=1}$ if $a$ is a nonzero square modulo $p$, and $\boxed{(a/p)=-1}$ otherwise. It depends only on the residue class of $a$.

Euler's criterion states that for $p\nmid a$,For a multiple of $p$, both the Legendre symbol and that positive power vanish modulo $p$, so the congruence extends to that case as well.

Gauss's lemma for quadratic residues states: if $p\nmid a$ and $m$ is the number of least positive residue classes among $a,2a,\dots ,((p-1)/2)a$ that exceed $p/2$, then $\boxed{(a/p)=(-1{)}^m}$.

For $a=2$ the displayed multiples are $2,4,\dots ,p-1$, already least positive residue classes. Those greater than $p/2$ correspond to $j>p/4$. Thus their number is $m=(p-1)/2-\lfloor p/4\rfloor$. For $p\equiv 1,3,5,7(\mathrm{mod}8)$, its parity is respectively even, odd, odd, even. Gauss's lemma therefore gives

Euler's criterion gives $(-1/p)=(-1{)}^{(p-1)/2}$. The Legendre symbol is multiplicative, so multiplying this sign by the result of (iv) yields

Suppose there are only finitely many primes $p_1,\dots ,p_r\equiv 3(\mathrm{mod}8)$, and let $N$ be their product. This is odd, so $N^2+2\equiv 3(\mathrm{mod}8)$. No listed prime divides this number, since reduction modulo any $p_i$ gives two. Every prime divisor $q$ is odd and does not divide $N$, and satisfies $N^2\equiv -2(\mathrm{mod}q)$. Thus $(-2/q)=1$, forcing $q\equiv 1$ or $3(\mathrm{mod}8)$ by (v).

A product of prime factors all congruent to one modulo eight could not be three modulo eight. More precisely, the product of factors congruent to three is three modulo eight exactly when their total exponent is odd. Thus at least one prime divisor $q\equiv 3(\mathrm{mod}8)$ occurs. It is not in the alleged complete list, a contradiction. Hence there are infinitely many primes congruent to three modulo eight.