Definition:Legendre Symbol
Definition
Let $p$ be an odd prime.
Let $a \in \Z$ be an integer.
Definition 1
The Legendre symbol $\paren {\dfrac a p}$ is defined as:
$\quad \paren {\dfrac a p} := \begin{cases} +1 & : a^{\frac {\paren {p - 1} } 2} \bmod p = 1 \\ \\
0 & : a^{\frac {\paren {p - 1} } 2} \bmod p = 0 \\ \\
-1 & : a^{\frac {\paren {p - 1} } 2} \bmod p = p - 1
\end{cases}$
Definition 2
The Legendre symbol $\paren {\dfrac a p}$ is defined as:
| \(\ds 0 \) | if $a \equiv 0 \pmod p$ | ||||||||
| \(\ds +1 \) | if $a$ is a quadratic residue of $p$ | ||||||||
| \(\ds -1 \) | if $a$ is a quadratic non-residue of $p$ |
Also presented as
For a given odd prime $p$, the Legendre symbol can be treated as a mapping:
- $f_p: \Z \to \set {-1, 0, 1}$
Some sources define it casually as a mapping $f : \mathbb P_{\ge 3} \times \Z \to \set {-1, 0, 1}$.
The only really complicated thing about this is its notation.
Also known as
The Legendre symbol for fixed prime $p$ is also known as the quadratic character modulo $p$.
However, that term is defined on $\mathsf{Pr} \infty \mathsf{fWiki}$ from this as simply whether an integer $a$ is a quadratic residue of $p$ or not, without assigning the result to an integer variable.
Hence Legendre symbol will be used throughout.
Examples
Example: $\paren {\frac 2 7}$
- $\paren {\dfrac 2 7} = 1$
Example: $\paren {\frac 3 7}$
- $\paren {\dfrac 3 7} = -1$
Also see
- Results about the Legendre symbol can be found here.
Source of Name
This entry was named for Adrien-Marie Legendre.
Historical Note
The Legendre symbol was introduced by Adrien-Marie Legendre in Paris in $1798$, during his partly successful attempt to prove the Law of Quadratic Reciprocity.
The function was later expanded into the Jacobi symbol, the Kronecker symbol, the Hilbert symbol and the Artin symbol.