This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000018567 Reproduction Date:
Legendre symbol (a/p) for various a (along top) and p (along left side). Only 0 ≤ a < p are shown, since due to the first property below any other a can be reduced modulo p. Quadratic residues are highlighted in yellow, and correspond precisely to the values 0 and 1.
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 non-quadratic residue (non-residue) is −1. Its value on zero is 0.
The Legendre symbol was introduced by Adrien-Marie Legendre in 1798^{[1]} 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.
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, which had been discovered earlier and was 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 a\mathrm{R}p, a\mathrm{N}p 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]}
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.
Let p and q be odd primes. Using the Legendre symbol, the quadratic reciprocity law can be stated concisely:
Many proofs of quadratic reciprocity are based on Legendre's formula
In addition, several alternative expressions for the Legendre symbol were devised in order to produce various proofs of the quadratic reciprocity law.
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.
Cryptography, Number theory, Mathematics, Law of quadratic reciprocity, Modular arithmetic
Computer science, Cryptography, Statistics, Discrete mathematics, Numerical analysis
Number theory, Probability, Algebraic number theory, Ancient Greece, Mersenne prime
Quadratic residue, Number theory, Cryptography, Legendre symbol, Modular arithmetic
Number theory, Completely multiplicative, Dirichlet L-function, Meromorphic function, Complex number
Computer science, Number theory, Music, Finite field, Law
France, Statistics, Paris, Number theory, Authority control
MathWorld, Fibonacci, Golden ratio, Indian mathematics, On-Line Encyclopedia of Integer Sequences
Mathematics, Number theory, ArXiv, Polynomial, Legendre symbol