Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 11H (Number Theory)

For an odd prime number $p$, the Legendre symbol isIf $p\nmid x$, multiplicativity of the Legendre symbol givesBoth factors belong to $\{1,-1\}$, so they are equal. Thus $(x^{-1}/p)=(x/p)$.

Gauss lemma states that if $p\nmid a$ and $m$ of the least positive residues ofexceed $p/2$, then $(a/p)=(-1{)}^m$.

To prove it, replace each residue exceeding $p/2$ by its negative, obtaining numbers $r_1,\dots ,r_{(p-1)/2}$ in $\{1,\dots ,(p-1)/2\}$. No two of them are equal modulo $p$: such an equality would give $ia\equiv \pm ja(\mathrm{mod}p)$, hence $i=j$ in the allowed range. They therefore permute $1,\dots ,(p-1)/2$, and multiplication givesCancel the nonzero factorial and apply Euler's criterion to obtain the lemma.

For $a=-1$, all $(p-1)/2$ least positive residues $p-1,p-2,\dots ,(p+1)/2$ exceed $p/2$. Hence the first supplementary law for quadratic reciprocity is

Write $\chi (x)=(x/p)$. Choose a quadratic nonresidue $a$. Multiplication by $a$ permutes ${\mathbb{F}}_p$, while multiplicativity of the Legendre symbol gives $\chi (ax)=-\chi (x)$. Thereforeso the complete Legendre-symbol sum is zero.

Since $4x(x+1)=(2x+1{)}^2-1$ and $\chi (4)=1$, the bijection $x\mapsto 2x+1$ reduces the next sum to ${\sum }_y\chi (y^2-1)$. Count pairs $(y,t)\in {\mathbb{F}}_p^2$ satisfying $t^2=y^2-1$. On one hand their number isOn the other hand $(y-t)(y+t)=1$, and every $u\in {\mathbb{F}}_p^{\times }$ gives exactly one pair by $y-t=u$, $y+t=u^{-1}$. There are therefore $p-1$ pairs, proving the quadratic Legendre-symbol correlation

For $1\le z\le p-2$, the indicator that both $z$ and $z+1$ are quadratic residues is $(1+\chi (z))(1+\chi (z+1))/4$. Summing and using the two identities above gives the number of consecutive nonzero quadratic residues modulo an odd prime