part-ii/2020-106/

[tripos-comments[bot]]

Part II 2020 Number Theory: Paper 3, Section II, 11H

https://questions.tripos.org/part-ii/2020-106/

[callumhobbis]

Sketch solution

(i): Just use the multiplicative property of the Legendre symbol.

(ii): In notes - using $a_j$ as in Gauss' lemma, for $1\leq j\leq\tfrac12(p-1)$, $(-1)_j=-j$ so all of them are negative, i.e. $(\tfrac{-1}p)=(-1)^{\tfrac12(p-1)} by Gauss.

(iii): The first bit uses the following trick: pick $b$ with $(\tfrac bp)=-1$, then show $-\sum_{x=1}^p(\tfrac xp)=\sum_{x=1}^p(\tfrac xp)$ by replacing that $-1$.

For the next bit, we need to use the trick of using $x^{-1}$: $x(x+1)\equiv x^2(1+x^{-1})\equiv 1+x^{-1}$ mod $p$.

Finally, note that the first bit tells us there are the same number of QRs and QNRs, and the second bit says there are $\tfrac12(p-1)$ pairs $1\leq z,z+1\leq p-1$ with $z,z+1$ either both QRs or both QNRs. We try every $z$, so they do split evenly between QRs and QNRs, giving $\tfrac14(p-1)$ of the pairs we want.

[FTcode]

Disagree with the final part as it's not even an integer when p is 3 mod 4.