Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 11I (Number Theory)

For an odd prime $p$, the Legendre symbol isEuler criterion states that

The Gauss lemma says that, for $p\nmid a$, if $m$ of the least positive residues oflie in $(p/2,p)$, thenTo prove it, replace every residue above $p/2$ by its negative. The resulting absolute residues are distinct up to sign and therefore form a permutation ofMultiplying the congruences givesCancel the nonzero factorial and apply Euler's criterion.

For $a=2$, the residues are $2,4,\dots ,p-1$. The number above $p/2$ iswhose parity gives the second supplementary law for quadratic reciprocityConsequently, for odd primes,The congruence is also soluble for $p=2$.

Suppose only finitely many primes $q_1,\dots ,q_r$ are congruent to $7$ modulo $8$, and setThenIf an odd prime $q$ divides $M$, then $n^2\equiv 2(\mathrm{mod}q)$, so part (a) givesSince their product $M$ is $7$ modulo $8$, at least one prime divisor $q$ is $7$ modulo $8$ to an odd power. Yet no listed $q_i$ divides $M$, because $n\equiv 0(\mathrm{mod}{q}_i)$ givesThis produces a new prime congruent to $7$ modulo $8$, a contradiction. HenceThis is the Euclid proof for infinitely many primes congruent to seven modulo eight.

Let $N=\lfloor \sqrt{x}\rfloor$ and formFor sufficiently large $x$, every factor is positive and at most $x$. Every odd prime divisor $p$ of $P$ makes $2$ a quadratic residue modulo $p$, so part (a) gives $p\equiv 1$ or $7(\mathrm{mod}8)$.

For an odd prime power $p^a$, the congruence $n^2\equiv 2(\mathrm{mod}{p}^a)$ has at most two residue classes, because each root modulo $p$ is simple and lifts uniquely. ThereforeSince $\log p/(p-1)\le \log 3/2$ for odd $p$,The prime $2$ contributes at most $N\log 2$, because $v_2(n^2-2)\le 1$. Ifthen, for all sufficiently large $x$, $2\log x\le N\log 3/2$ and hence

On the other hand, the product contains at least $N/3$ factors for large $N$, and every one satisfiesonce $x$ is sufficiently large. ThusComparing the two estimates givesfor every sufficiently large $x$. This is the elementary logarithmic lower bound for primes in the quadratic-residue classes of two.