Legendre symbol
From Number
Definition
Suppose 
is a prime number and 
is an integer. The Legendre symbol of modulo , denoted 
is defined to be:
-
if divides .
-
if is a quadratic residue modulo , i.e., does not divide and 
has an integer solution for 
.
-
if is a quadratic nonresidue modulo , i.e., does not divide and has no integer solution for .
The Legendre symbol makes sense only relative to a prime number, but it has a generalization called the Jacobi symbol which allows the modulus to be any integer. Thus, the Legendre symbol can also be defined as the restriction of the Jacobi symbol to cases where the modulus is prime.
The Legendre symbol is also a special case of a Dirichlet character modulo .
Facts
- The Legendre symbol is multiplicative in its top portion if the prime is fixed. In other words:
- Quadratic reciprocity relates the Legendre symbol values of two distinct odd primes modulo each other.
