= Solution
For the <odd prime> $p$, the <Fermat-Euler theorem> gives $x^{p-1}\equiv1\pmod p$. Therefore the <residue class> $z=x^{(p-1)/2}$ obeys $(z-1)(z+1)\equiv0\pmod p$. Since a <prime number> dividing a product divides one of its factors,
$$
\boxed{x^{(p-1)/2}\equiv1\text{ or }-1\pmod p.}
$$
If $x$ is a <quadratic residue>, choose $y$ with $y^2\equiv x\pmod p$. Then $y$ is nonzero modulo $p$, and <Fermat's little theorem> gives
$$
\boxed{x^{(p-1)/2}\equiv y^{p-1}\equiv1\pmod p.}
$$
This proves the <quadratic residue> direction of <Euler's criterion>.
Back to article page
