Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / C / C2 / a

A square residue modulo $p$ is a congruence class represented by $x^2$ for some integer $x$. For the final all-primes solvability statement, zero is included as a square. The Legendre symbol distinguishes the zero class from the nonzero square and nonsquare classes:When the term quadratic residue is reserved for nonzero classes, the zero case must be stated separately, as in this definition.

Euler's criterion states that, for an odd prime $p$ and $p\nmid a$,Thus this power is congruent to one for a nonzero square and to minus one for a nonsquare. The congruence also holds when $p\mid a$ if both sides are taken to be zero.

For distinct odd primes $p,q$, quadratic reciprocity isThe usual supplementary laws areThe first supplement also follows immediately by inserting $a=-1$ into Euler's criterion.

If $p$ divides $a$ or $b$, it divides their product and both sides of the proposed identity are zero. Otherwise use Euler's criterion and the ordinary exponent rule:Both sides are in $\{1,-1\}$, and these two values are distinct modulo the odd prime $p$. Hence the congruence is an equality: