Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 1 / 1G (Number Theory)

For an odd prime number $p$, the Legendre symbol is zero when $p\mid a$, one when $a$ is a nonzero quadratic residue modulo $p$, and minus one otherwise. The number-theoretic Gauss lemma says that, for $p\nmid a$, $(a/p)=(-1{)}^r$, where $r$ counts those least positive residues of $a,2a,\dots ,(p-1)a/2$ exceeding $p/2$.

For $a=2$, the residues are simply $2,4,\dots ,p-1$, so $r=(p-1)/2-\lfloor p/4\rfloor$. Examining the four odd residue classes modulo eight givesNow $2^m\equiv -1(\mathrm{mod}p)$ and $p$ is odd. The multiplicative order $d$ of $2$ divides $2m$ but not $m$. Since $m$ is a power of two, every proper divisor of $2m$ divides $m$, whence $d=2m$. Lagrange's theorem for finite groups gives $2m\mid p-1$. Because $m\ge 4$, this implies $p\equiv 1(\mathrm{mod}8)$, so the supplementary law just proved gives $(2/p)=1$. By Euler's criterion, $2^{(p-1)/2}\equiv 1(\mathrm{mod}p)$, and consequently $2m\mid (p-1)/2$. Therefore