# Statements Let $p$ be an odd prime. Then for $a\in \mathbb{Z}$ such that $p \not \mid a$, $a^{\frac{(p-1)}{2}} \equiv \begin{cases} 1 & \text{if } a \text{ is a quadratic residue } \mod p, \\ - 1& \text{otherwise.} \end{cases}$ In terms of the [[Legendre symbol]], this reads equivalently as $\left( \frac{a}{p} \right) \equiv a^{\frac{(p-1)}{2}} \mod p.$ # Proofs ###### Sketch - By [[Fermat's little theorem]], it suffices to show that $\left( \frac{a}{p} \right)a^{\frac{(p-1)}{2}} \equiv 1$. - By [[Wilson's theorem]], it suffices to show that $(p-1)! \equiv -\left( \frac{a}{p} \right)a^{\frac{(p-1)}{2}}$. - If $a$ is not a quadratic residue modulo $p$, then $x^{2}\equiv a\mod{p}$ has no solutions for $x\in\{1,2,\dots,p-1\}$. Since $\mathbb{Z}/p\mathbb{Z}$ is a field, the terms in $(p-1)!$ form $(p-1)/2$ pairs of distinct terms that multiply to $a$ modulo $p$ which yields $a^{(p-1)/2}$. - If $a$ is a quadratic residue, by [[Quadratic residues modulo prime|square roots lemma]] there are $2$ solutions to $x^{2} \equiv a$, denote $x$ and $p-x$. Note that $x(p-x)\equiv -a$ while the remaining terms form $(p-3)/2$ pairs of distinct terms that multiply to $a$ modulo $p$ which yields $-a a^{(p-3)/2}\equiv a^{(p-1)/2}$.