Legendre symbol

The Legendre symbol, named after the French mathematician Adrien-Marie Legendre, is used in connection with factorization and quadratic residues.

Definition

If $p$ is an odd prime number and $a$ is an integer, then the Legendre symbol

$\left(\frac{a}{p}\right)$

is:

• 0 if $p$ divides $a$;
• 1 if $a$ is a square modulo $p$ — that is to say there exists an integer $k$ such that $k^2\equiv a(\mathrm{mod}p)$, or in other words $a$ is a quadratic residue modulo $p$;
• −1 if $a$ is not a square modulo $p$, or in other words $a$ is not a quadratic residue modulo $p$.

Properties of the Legendre symbol

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

1. $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ (it is a completely multiplicative function in its top argument)
2. If $a\equiv b(\mathrm{mod}p)$, then $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$
3. $\left(\frac{1}{p}\right)=1$
4. $\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2}=\{\begin{array}{ll}1& \text{if }p\equiv 1(\mathrm{mod}4)\\ -1& \text{if }p\equiv 3(\mathrm{mod}4)\end{array}$
5. $\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}=\{\begin{array}{ll}1& \text{if }p\equiv 1\text{ or }7(\mathrm{mod}8)\\ -1& \text{if }p\equiv 3\text{ or }5(\mathrm{mod}8)\end{array}$
6. If $q$ is an odd prime then $\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)(-1{)}^{((p-1)/2)((q-1)/2)}$

The last property is known as the law of quadratic reciprocity. The properties 4 and 5 are traditionally known as the supplements to quadratic reciprocity.

The Legendre symbol is related to Euler's criterion and Euler proved that

$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(\mathrm{mod}p)$

External links

• Wikipedia