Values of Legendre Symbol

Theorem

Let $a \in \Z$, and let $p$ be an odd prime.

Let $\displaystyle \left({\frac{a}{p}}\right) = a^{\frac{(p-1)}{2}} \pmod p$ be the Legendre symbol.

Then:

$\left({\dfrac{a}{p}}\right) = \begin{cases} 0 & : a \,\bmod\, p = 0 \\ +1 & : \exists x \in \Z: x^2 \equiv a \pmod{p} \\ -1 & : \text {otherwise} \end{cases}$

Proof

Let $b = a^{\frac{(p-1)}{2}}$.

We have that $b^2 = a^{p - 1}$.

If $b^2$ divides $p$, then $b \,\bmod\, p = 0$.

Otherwise, from Fermat's Little Theorem, $b^2 \equiv 1 \pmod p$.

That is, $b^2 - 1 \equiv 0 \pmod p$.

Consider $b^2 - 1 = \left({b+1}\right) \left({b-1}\right)$ from Difference of Two Squares.

So either $b+1$ divides $p$ or $b-1$ does.

(They can't both do, as they have a difference of $2$, and $p$ is an odd prime.

From Congruence Modulo Negative Number‎, we have that $p-1 \equiv -1 \pmod p$.

Hence the result.

$\blacksquare$

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.4$: Exercise $26$