Legendre symbol
Definition

Let p {\displaystyle p} be an odd prime number. An integer a {\displaystyle a} is a quadratic residue modulo p {\displaystyle p} if it is congruent to a perfect square modulo p {\displaystyle p} and is a quadratic nonresidue modulo p {\displaystyle p} otherwise. The Legendre symbol is a function of a {\displaystyle a} and p {\displaystyle p} 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. 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 R p, a 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). For fixed p, the sequence (0 p), (1 p), (2 p), … {\displaystyle \left({\tfrac {0}{p}}\right),\left({\tfrac {1}{p}}\right),\left({\tfrac {2}{p}}\right),\ldots } is periodic with period p and is sometimes called the Legendre sequence. Each row in the following table exhibits periodicity, just as described.
startend:quotation, punctuation:no_comma