Legendre symbol

related topics
{math, number, function}
{law, state, case}

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 non-residue is −1.

The Legendre symbol was introduced by Adrien-Marie 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.



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 non-residue modulo p.

For typographical convenience, the Legendre symbol is sometimes written as (a|p) or (a/p). The sequence (a|p) 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 ▸

related documents
Axiom of pairing
Functional analysis
Elementary group theory
Unicity distance
Splitting lemma
Haar measure
Extended real number line
Richard's paradox
Lagrange inversion theorem
Examples of groups
Statistical independence
Referential transparency (computer science)
Meromorphic function
Assignment problem
Mathematical model
Ring (mathematics)
Quotient group
Extended Backus–Naur Form
Queue (data structure)
Presburger arithmetic
Tree (graph theory)
XSL Transformations
Chain rule
Oracle machine