Past exam of the mathematics course of the University of Cambridge / 2001 / ib / Paper 2 / 17B / Solution

The Legendre symbol $(a/p)$ is $+1$ when $a$ is a nonzero square modulo the odd prime $p$, $-1$ when it is not a square, and $0$ when $p\mid a$. For the coprime case, Euler's criterion statesWrite $h=(p-1)/2$. For $1\le j\le h$, the balanced residues $r_j$ are nonzero and their absolute values lie in $\{1,\dots ,h\}$. If $|r_j|=|r_k|$, then $aj\equiv \pm ak(\mathrm{mod}p)$. Cancel $a$. The plus sign forces $j=k$; the minus sign would require $j+k=p$, impossible because $j+k\le p-1$. Thus the absolute residues form a permutation of $1,\dots ,h$. If exactly $l$ are negative, multiplying givesSince $p$ does not divide $h!$, cancellation and Euler's criterion prove Gauss's lemma:The two signs are distinct modulo the odd prime, so this congruence identifies the integer symbol itself.

For $a=2$, the balanced representative of $2j$ is negative precisely when $j>p/4$, giving $l=(p-1)/2-\lfloor p/4\rfloor$. Checking the four odd residue classes modulo eight gives even $l$ for $p\equiv 1,7$ and odd $l$ for $p\equiv 3,5$. HenceThis is the quadratic character of two obtained from the lemma.

Let $P=p_1\cdots p_m$ and $N=8P^2-1$. If a prime $q$ divides $N$, then $q$ is odd and cannot divide $P$. Moreoverso $2$ has an explicit nonzero square root modulo $q$. The criterion just proved forces every prime divisor of $N$ into the classes $1$ or $7$ modulo eight. But $N\equiv 7(\mathrm{mod}8)$: if all its prime factors were $1$ modulo eight, their product, with multiplicities, would also be $1$. Thus at least one prime divisor is $7$ modulo eight. No listed $p_i$ divides $N$, because $N\equiv -1(\mathrm{mod}{p}_i)$. This always produces another such prime, proving infinitely many primes are congruent to seven modulo eight, the Euclid proof for infinitely many primes congruent to seven modulo eight.