In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo a prime number p: its value on a (nonzero) quadratic residue mod p is 1 and on a quadratic nonresidue is −1.
The Legendre symbol was introduced by AdrienMarie Legendre in 1798^{[1]} in the course of proving the law of quadratic reciprocity. Its generalizations 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.
Contents
Definition
Let p be an odd prime number. An integer a is a quadratic residue modulo p if it is congruent to a perfect square modulo p and is a quadratic nonresidue modulo p otherwise. The Legendre symbol is a function of a and p defined as follows:
Legendre's original definition was by means of an explicit formula:
By Euler's criterion that had been discovered earlier and known to Legendre, these two definitions are equivalent.^{[2]} 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 aRp, aNp according to whether a is a residue or a nonresidue modulo p.
For typographical convenience, the Legendre symbol is sometimes written as (ap) or (a/p). The sequence (ap) for a equal to 0,1,2,... is periodic with period p and is sometimes called the Legendre sequence, with {0,1,−1} values occasionally replaced by {1,0,1} or {0,1,0}.^{[3]}
Properties of the Legendre symbol
Full article ▸
