Past exam of the options II course of the University of Oxford / 2009 / C / C2 / iv / Solution

For $a=2$, the least positive residues in Gauss lemma for quadratic residues are simply $2,4,\dots ,p-1$. The number exceeding $p/2$ isFor $p\equiv 1,3,5,7(\mathrm{mod}8)$, respectively, this count is even, odd, odd, even. Substituting these parities into the lemma gives