Definition:Legendre Symbol/Definition 1

Definition

Let $p$ be an odd prime.

Let $a \in \Z$.

The Legendre symbol $\paren {\dfrac a p}$ is defined as:

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

where $x \bmod y$ denotes the modulo operation.

Also see

• Equivalence of Definitions of Legendre Symbol

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.

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $47$