Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 2 / 1G / Solution

For an odd prime $p$, the Legendre symbol isGauss lemma says that if $p\nmid a$ and $N$ of the least positive residues ofexceed $p/2$, then $(a/p)=(-1{)}^N$.

For $a=2$, none of $2,4,\dots ,p-1$ needs reduction modulo $p$, and the terms exceeding $p/2$ are those with $j>p/4$. HenceChecking $p\equiv 1,3,5,7(\mathrm{mod}8)$ shows that $N$ has the same parity as $(p^2-1)/8$. Therefore

By quadratic reciprocity, and because $149\equiv 1(\mathrm{mod}4)$,The three factors are $-1,1,1$, respectively, so