# Equivalence of Definitions of Legendre Symbol

## Theorem

Let $p$ be an odd prime.

Let $a \in \Z$.

The following definitions of the concept of Legendre Symbol are equivalent:

### Definition 1

The Legendre symbol $\left({\dfrac a p}\right)$ is defined as:

$\left({\dfrac a p}\right) := \begin{cases} +1 & : a^{\frac{(p - 1)} 2} \bmod p = 1 \\ 0 & : a^{\frac{(p - 1)} 2} \bmod p = 0 \\ -1 & : a^{\frac{(p - 1)} 2} \bmod p = p - 1 \end{cases}$

### Definition 2

The Legendre symbol $\left({\dfrac a p}\right)$ is defined as:

$\left({\dfrac a p}\right) := a^{\frac{(p - 1)} 2} \bmod p$

## Proof

From Integer to Power of $\dfrac {p - 1} 2$ Modulo $p$, one of the following cases holds:

$(1): \quad a^{\frac{(p - 1)} 2} \bmod p = 0$
$(2): \quad a^{\frac{(p - 1)} 2} \bmod p = 1$
$(3): \quad a^{\frac{(p - 1)} 2} \bmod p = p - 1$

Let $\paren {\dfrac a p}$ be defined as the Legendre symbol by definition 1:

The Legendre symbol $\left({\dfrac a p}\right)$ is defined as:

$\left({\dfrac a p}\right) := \begin{cases} +1 & : a^{\frac{(p - 1)} 2} \bmod p = 1 \\ 0 & : a^{\frac{(p - 1)} 2} \bmod p = 0 \\ -1 & : a^{\frac{(p - 1)} 2} \bmod p = p - 1 \end{cases}$
$p - 1 \pmod p = -1$

Thus $\paren {\dfrac a p}$ is the Legendre symbol by definition 2:

The Legendre symbol $\left({\dfrac a p}\right)$ is defined as:

$\left({\dfrac a p}\right) := a^{\frac{(p - 1)} 2} \bmod p$

$\blacksquare$