Topics Register • News • History • How to • Sequences statistics • Template prototypes

# Legendre symbol

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

## Definition

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

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

is:

• 0 if $\displaystyle{ p }$ divides $\displaystyle{ a }$;
• 1 if $\displaystyle{ a }$ is a square modulo $\displaystyle{ p }$ — that is to say there exists an integer $\displaystyle{ k }$ such that $\displaystyle{ k^2 \equiv a \pmod{p} }$, or in other words $\displaystyle{ a }$ is a quadratic residue modulo $\displaystyle{ p }$;
• −1 if $\displaystyle{ a }$ is not a square modulo $\displaystyle{ p }$, or in other words $\displaystyle{ a }$ is not a quadratic residue modulo $\displaystyle{ 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. $\displaystyle{ \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 $\displaystyle{ a \equiv b \pmod{p} }$, then $\displaystyle{ \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right) }$
3. $\displaystyle{ \left(\frac{1}{p}\right) = 1 }$
4. $\displaystyle{ \left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} 1 & \text{if } p \equiv 1 \pmod{4} \\ -1 & \text{if } p \equiv 3 \pmod{4} \end{cases} }$
5. $\displaystyle{ \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} 1 & \text{if } p \equiv 1 \text { or } 7 \pmod{8} \\ -1 & \text{if } p \equiv 3 \text{ or } 5 \pmod{8} \end{cases} }$
6. If $\displaystyle{ q }$ is an odd prime then $\displaystyle{ \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

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