Past exam of the short options course of the University of Oxford / 2014 / 1 / a / iii

Gauss's lemma states that, for $p\nmid a$, if $N$ of the least positive residues of $a,2a,\dots ,((p-1)/2)a$ exceed $p/2$, then $(a/p)=(-1{)}^N$.

For $a=2$, the residues are simply $2,4,\dots ,p-1$, with no reduction needed. Write $m=(p-1)/2$. A term $2j$ exceeds $p/2$ exactly when $j>p/4$, soIf $p$ is congruent to $1,3,5,7$ modulo eight, the parity of this count is respectively even, odd, odd, even. Gauss's lemma therefore givesThis proves the second supplementary law for quadratic reciprocity, rather than merely applying it.