Legendre symbol
|
|
The Legendre symbol is used by mathematicians in the area of number theory, particularly in the fields of factorization and quadratic residues. It is named after the French mathematician Adrien-Marie Legendre.
Definition
The Legendre symbol is a special case of the Jacobi symbol. It is defined as follows:
If p is a 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 k2 ≡ a (mod p), or a is a quadratic residue modulo p
- −1 if a is not a square modulo p, or 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)^{\left(\frac{p-1}{2}\right)}<math>, i.e. = 1 if p ≡ 1 (mod 4) and = −1 if p ≡ 3 (mod 4)
- <math>
\left(\frac{2}{p}\right) = (-1)^{\left(\frac{p^2-1}{8}\right)}<math>, i.e. = 1 if p ≡ 1 or 7 (mod 8) and = −1 if p ≡ 3 or 5 (mod 8)
- <math>
\left(\frac{a}{2}\right)<math> = 1 for all odd a and 0 for all even a
- If q is an odd prime then <math>
\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)} <math>
The last property is known as the law of quadratic reciprocity.
The Legendre symbol is related to Euler's criterion and Euler proved that
- <math>
\left(\frac{a}{p}\right) \equiv a^{\left(\frac{p-1}{2}\right)}\pmod p <math>
Additionally, the Legendre symbol is a Dirichlet character.
Related functions
The Jacobi symbol is a generalization of the Legendre symbol that allows composite bottom numbers.de:Legendre-Symbol es:Símbolo de Legendre fr:Symbole de Legendre it:Simbolo di Legendre pl:Symbol Legendre'a sv:Legendresymbolen