Legendre symbol


In number theory, the Legendre symbol is a function of and defined as
where is an odd prime number and is a positive integer that may or may not be a quadratic residue mod p. The Legendre symbol is a multiplicative function
The Legendre symbol was introduced by Adrien-Marie Legendre in 1797 or 1798 in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol and Dirichlet characters of higher order. The notational convenience of the Legendre symbol inspired introduction of several other "symbols" used in algebraic number theory, such as the Hilbert symbol and the Artin symbol.

Definition

Legendre's original definition was by means of the explicit formula
By Euler's criterion, which had been discovered earlier and was known to Legendre, these two definitions are equivalent. Thus Legendre's contribution lay in introducing a convenient notation that recorded quadratic residuosity of a mod p. For the sake of comparison, Gauss used the notation aR''p, a''Np according to whether a is a residue or a non-residue modulo p. For typographical convenience, the Legendre symbol is sometimes written as or. For fixed p, the sequence is periodic with period p and is sometimes called the Legendre sequence. Each row in the following table exhibits periodicity, just as described.

Properties of the Legendre symbol

There are a number of useful properties of the Legendre symbol which, together with the law of quadratic reciprocity, can be used to compute it efficiently.

Sums of Legendre symbols

Sums of the form, typically taken over all integers in the range for some function, are a special case of character sums. They are of interest in the distribution of quadratic residues modulo a prime number.

Legendre symbol and quadratic reciprocity

Let p and q be distinct odd primes. Using the Legendre symbol, the quadratic reciprocity law can be stated concisely:
Many proofs of quadratic reciprocity are based on Euler's criterion
In addition, several alternative expressions for the Legendre symbol were devised in order to produce various proofs of the quadratic reciprocity law.

Related functions

  • The Jacobi symbol is a generalization of the Legendre symbol that allows for a composite second argument n, although n must still be odd and positive. This generalization provides an efficient way to compute all Legendre symbols without performing factorization along the way.
  • A further extension is the Kronecker symbol, in which the bottom argument may be any integer.
  • The power residue symbol generalizes the Legendre symbol to higher power n. The Legendre symbol represents the power residue symbol for n = 2.

Computational example

The above properties, including the law of quadratic reciprocity, can be used to evaluate any Legendre symbol. For example:
Or using a more efficient computation:
The article Jacobi symbol has more examples of Legendre symbol manipulation.
Since no efficient factorization algorithm is known, but efficient modular exponentiation algorithms are, in general it is more efficient to use Legendre's original definition, e.g.
using repeated squaring modulo 331, reducing every value using the modulus after every operation to avoid computation with large integers.

Table of values

The following is a table of values of Legendre symbol with p ≤ 127, a ≤ 30, p odd prime.
123456789101112131415161718192021222324252627282930
31−101−101−101−101−101−101−101−101−101−10
51−1−1101−1−1101−1−1101−1−1101−1−1101−1−110
711−11−1−1011−11−1−1011−11−1−1011−11−1−1011
111−1111−1−1−11−101−1111−1−1−11−101−1111−1−1−1
131−111−1−1−1−111−1101−111−1−1−1−111−1101−111
1711−11−1−1−111−1−1−11−111011−11−1−1−111−1−1−11
191−1−11111−11−11−1−1−1−111−101−1−11111−11−11
231111−11−111−1−111−1−11−11−1−1−1−101111−11−1
291−1−11111−11−1−1−11−1−11−1−1−11−11111−1−1101
3111−111−11111−1−1−11−11−1111−1−1−1−11−1−11−1−1
371−111−1−11−11111−1−1−11−1−1−1−11−1−1−11111−11
4111−111−1−1111−1−1−1−1−11−11−111−11−11−1−1−1−1−1
431−1−11−11−1−1111−111111−1−1−11−1111−1−1−1−1−1
471111−11111−1−11−11−1111−1−11−1−111−111−1−1
531−1−11−111−1111−11−1111−1−1−1−1−1−111−1−111−1
591−1111−11−11−1−11−1−1111−11111−1−111111−1
611−1111−1−1−11−1−111111−1−111−11−1−11−11−1−1−1
671−1−11−11−1−111−1−1−11111−11−1111111−1−11−1
71111111−1111−11−1−111−1111−1−1−111−11−111
731111−11−111−1−11−1−1−11−111−1−1−1111−11−1−1−1
7911−111−1−11111−11−1−11−1111111−111−1−1−1−1
831−111−1−11−11111−1−1−111−1−1−11−11−1111111
8911−111−1−11111−1−1−1−1111−1111−1−11−1−1−1−1−1
971111−11−111−111−1−1−11−11−1−1−11−111−11−1−1−1
1011−1−1111−1−11−1−1−111−111−11111111−1−1−1−11
10311−11−1−1111−1−1−11111111−1−1−11−111−1111
1071−111−1−1−1−1111111−11−1−11−1−1−11−11−11−111
1091−1111−11−11−1−11−1−111−1−1−1111−1−111111−1
11311−11−1−1111−11−11111−11−1−1−11−1−111−11−11
12711−11−1−1−111−11−11−111111−111−1−111−1−1−11