Proof that Legendre symbol $\Big(\frac{a}{p}\Big)$ is $a^{\frac{p-1}{2}}$

Question

When $p$ is a prime, we know that Legendre symbol of $a$ is $$\left(\frac{a}{p}\right) = a^{({p-1})/{2}}$$ Suppose $a$ is a square, then $a = x^2$ for some $x$. Therefore, $a^{\frac{p-1}{2}} = x^{p-1} = 1$ by Fermat's little theorem. But if $a$ is not a square, then how to prove that $a^{\frac{p-1}{2}} = -1$?

Answer 1

First of all, there are two commonly used definitions of the Legendre symbol $\left( \frac ap \right)$. One is simply that $$\left( \frac ap \right) \equiv a^\tfrac{p-1}{2} \pmod p$$ for any integer $a$ and any odd prime $p$. Of course, this congruence only defines $\left( \frac ap \right)$ modulo $p$, but by convention (and for convenience) we normally choose the solution closest to zero.

The other definition is that $$ \left( \frac ap \right) = \begin{cases} \phantom+ 0 & \text{if } a \equiv 0 \pmod p, \\ \phantom+ 1 & \text{if } a \not\equiv 0 \pmod p \text{ and } a \equiv b^2 \pmod p \text{ for some } b, \text{ and} \\ -1 & \text{otherwise.} \end{cases}$$

By Euler's criterion, these two definitions are equivalent, which I assume is what you're trying to prove. The Wikipedia page I just linked to already gives a pretty good description of how to prove this, so let me just essentially recap it here:

---

The case when $a \equiv 0 \pmod p$ is trivial, since it's an elementary result of modular arithmetic that $a^n \equiv 0^n \equiv 0 \pmod p$ for any positive exponent $n$ in this case.

By Fermat's little theorem, we know that $a^p \equiv a \pmod p$. If $a \not\equiv 0 \pmod p$, then it directly follows that $a^{p-1} \equiv 1 \pmod p$. Rewriting this as $a^{p-1}-1 \equiv 0 \pmod p$ and factoring (using the fact that $p$ is odd by definition, and thus $p-1$ is even) gives $$\left( a^\frac{p-1}{2} + 1 \right)\left( a^\frac{p-1}{2} - 1 \right) \equiv 0 \pmod p.$$ Since the integers modulo a prime $p$ have no zero divisors, one of the factors on the left hand side must be congruent to zero for this congruence to hold, and thus $a^{(p-1) \mathop/ 2} \equiv \pm1 \pmod p$ for all $a \not\equiv 0 \pmod p$. To complete the proof, all we need to do is figure out which case holds for each non-zero $a$.

If $a \equiv b^2 \pmod p$ for some integer $b$, then $a^{(p-1) \mathop/ 2} \equiv (b^2)^{(p-1) \mathop/ 2} = b^{\,p-1} \equiv 1 \pmod p,$ where the last congruence again follows from Fermat's little theorem. Thus, $a^{(p-1) \mathop/ 2} \equiv 1 \pmod p$ for all quadratic residues $a$ modulo $p$.

Finally, to show that $a^{(p-1) \mathop/ 2} \equiv -1 \pmod p$ for all quadratic non-residues, we can apply Lagrange's theorem to show that:

• $a^{(p-1) \mathop/ 2} \equiv 1$ has at most $(p-1) \mathop/ 2$ solutions modulo $p$, and
• $b^2 \equiv a$ can have at most two solutions modulo $p$ for each $a$.

Thus, since there are $p-1$ non-zero integers $b$ modulo $p$, then by the pigeonhole principle there must be at least $(p-1) \mathop/ 2$ non-zero integers $a$ modulo $p$ for which $b^2 \equiv a \pmod p$ has a solution (and which thus are quadratic residues). Combining this with the earlier results above, we can see that there must be exactly $(p-1) \mathop/ 2$ non-zero quadratic residues modulo $p$, and that those must be the only solutions to $a^{(p-1) \mathop/ 2} \equiv 1 \pmod p$. Thus, for all other non-zero $a$, we must have $a^{(p-1) \mathop/ 2} \equiv -1 \pmod p$, since we have already proved that those are the only possible options.