[proofplan] We handle the case $p \mid a$ (both sides vanish mod $p$) and the case $(a, p) = 1$ separately. In the coprime case, Fermat's Little Theorem implies $a^{(p-1)/2} \equiv \pm 1 \pmod p$. We show that every quadratic residue satisfies $a^{(p-1)/2} \equiv 1$. Since there are exactly $(p-1)/2$ quadratic residues by the [Count of Quadratic Residues](/theorems/1714) and the polynomial $X^{(p-1)/2} - 1$ has at most $(p-1)/2$ roots over $\mathbb{F}_p$ by [Lagrange's theorem for polynomial congruences](/theorems/1709), the quadratic residues account for all solutions of $a^{(p-1)/2} \equiv 1$, forcing non-residues to satisfy $a^{(p-1)/2} \equiv -1$. [/proofplan] [step:Handle the degenerate case $p \mid a$] Suppose $p \mid a$. Then $a \equiv 0 \pmod p$, so \begin{align*} a^{\frac{p-1}{2}} \equiv 0 \pmod p, \end{align*} and by definition of the Legendre symbol, $\left(\tfrac{a}{p}\right) = 0$. Both sides of the claimed congruence equal $0$, so equality holds. [/step] [step:Reduce the coprime case to showing $a^{(p-1)/2} \equiv \pm 1 \pmod p$] Assume $(a, p) = 1$. By Fermat's Little Theorem (a direct consequence of $(\mathbb{Z}/p\mathbb{Z})^\times$ having order $p - 1$, see [$(\mathbb{Z}/p\mathbb{Z})^\times$ is Cyclic](/theorems/1710)), \begin{align*} a^{p-1} \equiv 1 \pmod p. \end{align*} Since $p$ is odd, $(p-1)/2 \in \mathbb{Z}$, and we may factor \begin{align*} 0 \equiv a^{p-1} - 1 = \left(a^{\frac{p-1}{2}}\right)^2 - 1 = \left(a^{\frac{p-1}{2}} - 1\right)\left(a^{\frac{p-1}{2}} + 1\right) \pmod p. \end{align*} By the [Prime Divisibility Lemma](/theorems/1698), $p$ divides one of the two factors, i.e., \begin{align*} a^{\frac{p-1}{2}} \equiv 1 \pmod p \quad \text{or} \quad a^{\frac{p-1}{2}} \equiv -1 \pmod p. \end{align*} It remains to show that the first case occurs precisely when $a$ is a quadratic residue. [guided] We are in the coprime case $(a, p) = 1$, so $a \pmod p$ is a unit in $(\mathbb{Z}/p\mathbb{Z})^\times$. Fermat's Little Theorem says any unit raised to the group order yields the identity: \begin{align*} a^{p-1} \equiv 1 \pmod p. \end{align*} Why is this equivalent to $a^{(p-1)/2} \equiv \pm 1$? We exploit that $p - 1$ is even (because $p$ is odd — an essential use of the hypothesis), so $(p-1)/2$ is a positive integer, and \begin{align*} a^{p-1} = \left(a^{\frac{p-1}{2}}\right)^2. \end{align*} Setting $b := a^{(p-1)/2} \pmod p$, we have $b^2 \equiv 1 \pmod p$. Factoring $b^2 - 1 = (b-1)(b+1)$ and applying the [Prime Divisibility Lemma](/theorems/1698) (with $p$ prime, so $p \mid (b-1)(b+1)$ forces $p \mid b-1$ or $p \mid b+1$): \begin{align*} b \equiv 1 \pmod p \quad \text{or} \quad b \equiv -1 \pmod p. \end{align*} So the two alternatives exhaust all possibilities. The remaining task is to match them with "$a$ is a quadratic residue" vs "$a$ is a non-residue". [/guided] [/step] [step:Show every quadratic residue satisfies $a^{(p-1)/2} \equiv 1 \pmod p$] Suppose $\left(\tfrac{a}{p}\right) = 1$, i.e., $a \equiv x^2 \pmod p$ for some $x \in \mathbb{Z}$ with $(x, p) = 1$ (coprimality follows because $(a, p) = 1$ and $p$ prime). Then \begin{align*} a^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} = x^{p-1} \equiv 1 \pmod p, \end{align*} where the last step uses Fermat's Little Theorem applied to $x$ (valid since $(x, p) = 1$). Thus every quadratic residue $a$ satisfies $a^{(p-1)/2} \equiv 1 \pmod p$. In particular, in the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$, every quadratic residue is a root of the polynomial \begin{align*} f(X) := X^{\frac{p-1}{2}} - 1 \in \mathbb{F}_p[X]. \end{align*} [/step] [step:Use Lagrange's polynomial bound to pin down all roots of $X^{(p-1)/2} - 1$] The polynomial $f(X) = X^{(p-1)/2} - 1 \in \mathbb{F}_p[X]$ has degree $(p-1)/2$, with leading coefficient $1$ (coprime to $p$). By [Lagrange's theorem for polynomial congruences](/theorems/1709), $f$ has at most $(p-1)/2$ roots in $\mathbb{F}_p$. By the [Count of Quadratic Residues](/theorems/1714), there are exactly $(p-1)/2$ quadratic residues in $(\mathbb{Z}/p\mathbb{Z})^\times$, and by the previous step each is a root of $f$. Thus $f$ has at least $(p-1)/2$ distinct roots. Combined with the upper bound from Lagrange, $f$ has exactly $(p-1)/2$ roots, and they are precisely the quadratic residues: \begin{align*} \{a \in (\mathbb{Z}/p\mathbb{Z})^\times : a^{\frac{p-1}{2}} \equiv 1 \pmod p\} = \{\text{quadratic residues}\}. \end{align*} [guided] The strategy here is a classical counting argument: we have a polynomial identity $a^{(p-1)/2} \equiv 1 \pmod p$, and we ask how many $a \in (\mathbb{Z}/p\mathbb{Z})^\times$ satisfy it. Two independent estimates squeeze the answer. **Upper bound (Lagrange).** The polynomial \begin{align*} f(X) = X^{\frac{p-1}{2}} - 1 \in \mathbb{F}_p[X] \end{align*} has degree $(p-1)/2$. Its leading coefficient is $1$, which is not divisible by $p$, so the hypothesis of [Lagrange's theorem for polynomial congruences](/theorems/1709) is met. Conclusion: at most $(p-1)/2$ residues $a \in \mathbb{Z}/p\mathbb{Z}$ satisfy $f(a) \equiv 0 \pmod p$. **Lower bound (counting residues).** The previous step showed every quadratic residue is a root of $f$. By the [Count of Quadratic Residues](/theorems/1714), there are exactly $(p-1)/2$ quadratic residues in $(\mathbb{Z}/p\mathbb{Z})^\times$, hence at least $(p-1)/2$ roots of $f$. The two bounds match, so equality holds and the roots of $f$ are *exactly* the quadratic residues. No non-residue satisfies $a^{(p-1)/2} \equiv 1 \pmod p$. Why is this tight? Lagrange's bound is sharp precisely when working over a field (here $\mathbb{F}_p$), which is where the primality hypothesis on $p$ enters. Over a non-prime modulus, the bound can fail (e.g., $X^2 - 1$ has four roots in $\mathbb{Z}/8\mathbb{Z}$), and correspondingly the count of quadratic residues is more subtle. [/guided] [/step] [step:Conclude that non-residues satisfy $a^{(p-1)/2} \equiv -1 \pmod p$] By Step 2, for every $a$ with $(a, p) = 1$ we have $a^{(p-1)/2} \equiv \pm 1 \pmod p$. By the previous step, $a^{(p-1)/2} \equiv 1 \pmod p$ iff $a$ is a quadratic residue. Hence if $a$ is a quadratic non-residue (so $\left(\tfrac{a}{p}\right) = -1$), then \begin{align*} a^{\frac{p-1}{2}} \equiv -1 \pmod p. \end{align*} Summarising: for $(a, p) = 1$, \begin{align*} a^{\frac{p-1}{2}} \equiv \left(\tfrac{a}{p}\right) \pmod p. \end{align*} Combined with the $p \mid a$ case in Step 1 (where both sides vanish mod $p$), the congruence holds for all $a \in \mathbb{Z}$, completing the proof. [/step]