Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ii/paper-3/11h/iii/solution

Write . Choose a quadratic nonresidue . Multiplication by permutes , while multiplicativity of the Legendre symbol gives . Therefore
so the complete Legendre-symbol sum is zero.
Since and , the bijection reduces the next sum to . Count pairs satisfying . On one hand their number is
On the other hand , and every gives exactly one pair by , . There are therefore pairs, proving the quadratic Legendre-symbol correlation
For , the indicator that both and are quadratic residues is . Summing and using the two identities above gives the number of consecutive nonzero quadratic residues modulo an odd prime

New to topics? Read the docs here!