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 of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1.
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.
if it is congruent to a perfect square modulo
defined as 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.
[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).
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.
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.
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.