# 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

- [math]\left(\frac{a}{p}\right)[/math]

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}≡*a*(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:

- [math]\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)[/math] (it is a completely multiplicative function in its top argument)
- If
*a*≡*b*(mod*p*), then [math]\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)[/math] - [math]\left(\frac{1}{p}\right) = 1[/math]
- [math]\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}[/math], i.e. = 1 if
*p*≡ 1 (mod 4) and = −1 if*p*≡ 3 (mod 4) - [math]\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}[/math], i.e. = 1 if
*p*≡ 1 or 7 (mod 8) and = −1 if*p*≡ 3 or 5 (mod 8) - If
*q*is an odd prime then [math]\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{ ((p-1)/2) ((q-1)/2) }[/math]

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

- [math]\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\,\pmod p[/math]