= Solution
For an odd prime $p$, the <Legendre symbol> is
$$
\left(\frac ap\right)=
\begin{cases}
0,&p\mid a,\\
1,&a\not\equiv0\pmod p\text{ is a quadratic residue},\\
-1,&a\text{ is a quadratic nonresidue}.
\end{cases}
$$
<Euler criterion> states that
$$
\boxed{
a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p.}
$$
If $p\mid a$, both sides vanish. Otherwise choose a <primitive root> $g$ and write $a\equiv g^m$. Since $g^{(p-1)/2}\equiv-1$,
$$
a^{(p-1)/2}\equiv(-1)^m.
$$
The power $g^m$ is a square exactly when $m$ is even, proving the criterion. Taking $a=-1$ gives the <first supplementary law for quadratic reciprocity>
$$
\boxed{\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}.}
$$
Back to article page
