Past exam of the probability, statistics and options I course of the University of Oxford / 2010 / C / 1 (C1)

The Legendre symbol isIt depends only on the residue class of $a$ modulo the odd prime $p$.

Euler's criterion statesFor $p\nmid a$, the sign is $+1$ precisely for a quadratic residue and $-1$ for a quadratic nonresidue. For $p\mid a$, both sides are zero.

Write $s=(a/p)$. If $p\mid a$, both sides of the proposed identity are zero. Otherwise $s=\pm 1$. The multiplicativity of the Legendre symbol and Euler's criterion giveFor the middle equality, Euler's congruence determines the sign exactly, since both the symbol and $s^{(p-1)/2}$ are in $\{1,-1\}$ and $p$ is odd.

Again $s=(a/p)\in \{1,-1\}$. By Euler's criterion, $(s/p)=s^{(p-1)/2}$. If $p\equiv 1(\mathrm{mod}4)$, the exponent is even and the answer is one. If $p\equiv 3(\mathrm{mod}4)$, it is odd and the answer is $s$. Hence