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

For an odd prime $p$, the Legendre symbol isEuler criterion states thatIf $p\mid a$, both sides vanish. Otherwise choose a primitive root $g$ and write $a\equiv g^m$. Since $g^{(p-1)/2}\equiv -1$,The power $g^m$ is a square exactly when $m$ is even, proving the criterion. Taking $a=-1$ gives the first supplementary law for quadratic reciprocity

Because $I$ and $A$ commute, the matrix binomial theorem givesFor prime $p$, every intermediate coefficient $\left(\genfrac{}{}{0ex}{}{p}{j}\right)$ is divisible by $p$, proving the prime-power binomial congruence for a matrix

Forone has $(I+A{)}^2=2A$ and $(I+A{)}^4=-4I$. If $p=4k+1$, thenso $(-4{)}^k\equiv 1(\mathrm{mod}p)$. If $p=4k-1$, then $A^p=-A$ andso $(-4{)}^k\equiv 2(\mathrm{mod}p)$.

By Euler criterion, $(\frac{2}{p})\equiv 2^{(p-1)/2}(\mathrm{mod}p)$. In either case the preceding congruence gives $(\frac{2}{p})=(-1{)}^k$. Since $(p^2-1)/8$ has the same parity as $k$ for $p=4k\pm 1$, this is the second supplementary law for quadratic reciprocity

Write $\chi (a)=(\frac{a}{p})$. When $p\equiv 1(\mathrm{mod}4)$, the first supplementary law for quadratic reciprocity gives $\chi (-1)=1$, so $\chi (p-a)=\chi (a)$. Pairing $a$ with $p-a$ givesThe sum of the nontrivial character $\chi$ over all nonzero residue classes is zero. Because its two half-sums are equal when $\chi (-1)=1$,Hence

By Euler criterion,Choose a primitive root $g$. For any integer $m$ not divisible by $p-1$,For $p>3$, the exponent $m=(p+1)/2$ satisfies $0<m<p-1$. ThereforeTogether with part (i), this is the weighted complete Legendre-symbol sum.

Put $H=(p-1)/2$. Because $p\equiv 7(\mathrm{mod}8)$, the supplementary laws giveLet $R$ and $N$ be the quadratic residues and nonresidues, respectively, among $1,\dots ,H$, and putSince $-1$ is a nonresidue, the complete set $Q$ of least positive quadratic residues isIf $u=|N|$, its sum is

Since $2$ is a residue, multiplication by two permutes $Q$ modulo $p$. Exactly the $u$ upper-half residues $p-n$ cross $p$ when doubled. Equality of the sums before and after reduction therefore givesComparing the two formulas yieldsAs $H=(p-1)/2$,This is the lower-half quadratic-residue sum for primes congruent to seven modulo eight.