In number theory, the Legendre symbol is a function of a {\displaystyle a} and p {\displaystyle p} defined as
( a p ) = { 1 if a is a quadratic residue modulo p and a ≢ 0 ( mod p ) , − 1 if a is a quadratic nonresidue modulo p , 0 if a ≡ 0 ( mod p ) . {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{if }}a{\text{ is a quadratic nonresidue modulo }}p,\\0&{\text{if }}a\equiv 0{\pmod {p}}.\end{cases}}}
where p {\displaystyle p} is an odd prime number and a {\displaystyle a} is a positive integer that may or may not be a quadratic residue mod p. The Legendre symbol is a multiplicative function. The Legendre symbol was introduced by Adrien-Marie Legendre in 1797 or 1798 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.
Definition Legendre's original definition was by means of the explicit formula
( a p ) ≡ a p − 1 2 ( mod p ) and ( a p ) ∈ { − 1 , 0 , 1 } . {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\quad {\text{ and }}\quad \left({\frac {a}{p}}\right)\in \{-1,0,1\}.}
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 whether a is a residue or a non-residue modulo p. Gauss' original notation used aRp for ( a p ) = 1 {\displaystyle ({\tfrac {a}{p}})=1} and aNp for ( a p ) = − 1 {\displaystyle ({\tfrac {a}{p}})=-1} . For typographical convenience, the Legendre symbol is sometimes written as (a | p) or (a/p). For fixed p, the sequence ( 0 p ) , ( 1 p ) , ( 2 p ) , … {\displaystyle ({\tfrac {0}{p}}),({\tfrac {1}{p}}),({\tfrac {2}{p}}),\ldots } is periodic with period p and is sometimes called the Legendre sequence (see above table).
Properties of the Legendre symbol 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.
Given a generator g ∈ F p ∗ {\displaystyle g\in \mathbb {F} _{p}^{*}} , if x = g r {\displaystyle x=g^{r}} , then x {\displaystyle x} is a quadratic residue if and only if r {\displaystyle r} is even. This shows that half of the elements in F p ∗ {\displaystyle \mathbb {F} _{p}^{*}} are quadratic residues. If p ≡ 3 mod 4 {\displaystyle p\equiv 3{\text{ mod }}4} then the fact that
… excerpt ends here. Continue reading the full article.
