Legendre symbol

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

( a p ) = { 1  if  a  is a quadratic residue modulo  p  and  a ≢ 0 ( mod p ) , − 1  if  a  is a quadratic non-residue modulo  p , 0  if  a ≡ 0 ( mod p ) .

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

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

Table of values

The following is a table of values of Legendre symbol (k/n) with n ≤ 127, k ≤ 30, n odd prime.

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.

The Legendre symbol is periodic in its first (or top) argument: if a ≡ b (mod p), then

The Legendre symbol is a completely multiplicative function of its top argument:

In particular, the product of two numbers that are both quadratic residues or quadratic non-residues modulo p is a residue, whereas the product of a residue with a non-residue is a non-residue. A special case is the Legendre symbol of a square:

When viewed as a function of a, the Legendre symbol (a/p) is the unique quadratic (or order 2) Dirichlet character modulo p.

The first supplement to the law of quadratic reciprocity:

The second supplement to the law of quadratic reciprocity:

Special formulas for the Legendre symbol (a/p) for small values of a:

For an odd prime p ≠ 3,

For an odd prime p ≠ 5,

The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... are defined by the recurrence F₁ = F₂ = 1, F_n+1 = F_n + F_n−1. If p is a prime number then

For example,

This result comes from the theory of Lucas sequences, which are used in primality testing. See Wall–Sun–Sun prime.

Legendre symbol and quadratic reciprocity

Let p and q be distinct odd primes. Using the Legendre symbol, the quadratic reciprocity law can be stated concisely:

( q p ) ( p q ) = ( − 1 ) p − 1 2 ⋅ q − 1 2 .

Many proofs of quadratic reciprocity are based on Legendre's formula

( a p ) ≡ a p − 1 2 ( mod p ) .

In addition, several alternative expressions for the Legendre symbol were devised in order to produce various proofs of the quadratic reciprocity law.

Gauss introduced the quadratic Gauss sum and used the formula

in his fourth and sixth proofs of quadratic reciprocity.

Kronecker's proof first establishes that

Reversing the roles of p and q, he obtains the relation between (p/q) and (q/p).

One of Eisenstein's proofs begins by showing that

Using certain elliptic functions instead of the sine function, Eisenstein was able to prove cubic and quartic reciprocity as well.

Related functions

The Jacobi symbol (a/n) is a generalization of the Legendre symbol that allows for a composite second (bottom) argument n, although n must still be odd and positive. This generalization provides an efficient way to compute all Legendre symbols without performing factorization along the way.

A further extension is the Kronecker symbol, in which the bottom argument may be any integer.

The power residue symbol (a/n)_n generalizes the Legendre symbol to higher power n. The Legendre symbol represents the power residue symbol for n = 2.

Computational example

The above properties, including the law of quadratic reciprocity, can be used to evaluate any Legendre symbol. For example:

( 12345 331 ) = ( 3 331 ) ( 5 331 ) ( 823 331 ) = ( 3 331 ) ( 5 331 ) ( 161 331 ) = ( 3 331 ) ( 5 331 ) ( 7 331 ) ( 23 331 ) = ( − 1 ) ( 331 3 ) ( 331 5 ) ( − 1 ) ( 331 7 ) ( − 1 ) ( 331 23 ) = − ( 1 3 ) ( 1 5 ) ( 2 7 ) ( 9 23 ) = − ( 1 3 ) ( 1 5 ) ( 2 7 ) ( 3 2 23 ) = − ( 1 ) ( 1 ) ( 1 ) ( 1 ) = − 1.

Or using a more efficient computation:

( 12345 331 ) = ( 98 331 ) = ( 2 ⋅ 7 2 331 ) = ( 2 331 ) = ( − 1 ) 331 2 − 1 8 = − 1.

The article Jacobi symbol has more examples of Legendre symbol manipulation.