Equivalence of Definitions of Legendre Symbol

From ProofWiki
Jump to navigation Jump to search

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}$


By Negative Number is Congruent to Modulus minus Number we have:

$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$