Legendre Symbol - Definition

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, 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, 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}.