Past exam of the options II course of the University of Oxford / 2012 / C / C2 / a

For an integer $a$ and an odd prime $p$, the Legendre symbol isThe value one refers to a nonzero quadratic residue; divisibility by $p$ is recorded separately by zero.

Euler's criterion states thatFor $p\nmid a$ this says that the power is $1$ for a quadratic residue and $-1$ for a quadratic nonresidue. When $p\mid a$, both sides are zero modulo $p$.

Euler's criterion givesIf either factor is divisible by $p$, both asserted values are zero. Otherwise the two values lie in $\{1,-1\}$, whose elements are distinct modulo an odd prime. The modular congruence is therefore equality:Finally, $a\equiv b(\mathrm{mod}p)$ means they give the same residue class and thus the same set of square-congruence solutions. Divisibility by $p$ is also identical. Hence $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$.