Definition:Legendre Symbol

The Legendre symbol is a function 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.

Definition

Legendre defined the symbol as follows:

Let $p$ be an odd prime.

Let $a \in \Z$.

Then:

$\displaystyle \left({\frac{a}{p}}\right) := a^{\frac{(p-1)}{2}} \pmod p$.

From Values of Legendre Symbol, we have that:

$\displaystyle \left({\frac a p}\right) = \begin{cases} 0& : a \equiv 0 \pmod{p} \\+1 & : a \not\equiv 0\pmod{p} \text{ and for some integer }x, x^2\equiv \;a \pmod{p} \\-1 & : \text{if there is no such } x \end{cases}$

From Euler's Criterion, this can be seen to be equivalent to:

$\displaystyle \left({\frac{a}{p}}\right) = \begin{cases} 0 & : a \equiv 0 \pmod{p} \\ +1 & : a \text{ is a quadratic residue of } p \\ -1 & : a \text{ is a quadratic non-residue of } p \end{cases}$

For a given $p$, the Legendre symbol is usually treated as a function $f_p: \Z \to \left\{{-1, 0, 1}\right\}$.

Applications

The Legendre Symbol can be used as a tool to finding whether a number is a Quadratic Residue (mod $p$) through the following conditions:

• $\displaystyle \left({\frac a p}\right) = 1$ iff $a$ is a Quadratic Residue mod $p$;
• $\displaystyle \left({\frac a p}\right) = -1$ iff $a$ is a Quadratic Non-Residue mod $p$.

This follows directly from the definitions of quadratic residue and quadratic non-residue, and Euler's Criterion.

Properties

There are a number of useful properties of the Legendre symbol which can be used to speed up calculations. They include:

• $\displaystyle \left({\frac{a b} p}\right) = \left({\frac a p}\right) \left({\frac b p}\right)$;

• If $a \equiv b \pmod p$, then $\displaystyle \left({\frac a p}\right) = \left({\frac b p}\right)$;

• $\displaystyle \left({\frac{a^2} p}\right) = 1$.

See Properties of Legendre Symbol.

Law of Quadratic Reciprocity

• If $p$ and $q$ are odd primes then:

$\displaystyle \left({\frac q p}\right) = \left({\frac p q}\right)(-1)^{(p-1)(q-1)/4}$.

This is called the Law of Quadratic Reciprocity.

• $\displaystyle \left({\frac{-1}{p}}\right) = (-1)^{(p-1)/2} = \begin{cases} +1 & : p \equiv 1\pmod{4} \\ -1 & : p \equiv 3\pmod{4} \end{cases}$

This is called the First Supplement to the Law of Quadratic Reciprocity.

• $\displaystyle \left({\frac{2}{p}}\right) = (-1)^{(p^2-1)/8} = \begin{cases} +1 & : p \equiv 1\text{ or }7 \pmod{8} \\ -1 & : p \equiv 3\text{ or }5 \pmod{8} \end{cases}$

This is called the Second Supplement to the Law of Quadratic Reciprocity.