Legendre symbol
Encyclopedia
In number theory
, the Legendre symbol is a multiplicative function
with values 1, −1, 0 that is a quadratic character modulo a prime number
p: its value on a (nonzero) quadratic residue mod p is 1 and on a quadratic non-residue is −1.
The Legendre symbol was introduced by Adrien-Marie Legendre
in 1798 in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol
and Dirichlet character
s 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.
. 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}.
, can be used to compute it efficiently.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, the Legendre symbol is a multiplicative function
Multiplicative function
In number theory, a multiplicative function is an arithmetic function f of the positive integer n with the property that f = 1 and whenevera and b are coprime, then...
with values 1, −1, 0 that is a quadratic character modulo a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
p: its value on a (nonzero) quadratic residue mod p is 1 and on a quadratic non-residue is −1.
The Legendre symbol was introduced by Adrien-Marie Legendre
Adrien-Marie Legendre
Adrien-Marie Legendre was a French mathematician.The Moon crater Legendre is named after him.- Life :...
in 1798 in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol
Jacobi symbol
The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in...
and Dirichlet character
Dirichlet character
In number theory, Dirichlet characters are certain arithmetic functions which arise from completely multiplicative characters on the units of \mathbb Z / k \mathbb Z...
s of higher order. The notational convenience of the Legendre symbol inspired introduction of several other "symbols" used in algebraic number theory
Algebraic number theory
Algebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...
, such as the Hilbert symbol
Hilbert symbol
In mathematics, given a local field K, such as the fields of reals or p-adic numbers, whose multiplicative group of non-zero elements is K×, the Hilbert symbol is an algebraic construction, extracted from reciprocity laws, and important in the formulation of local class field theory...
and the Artin symbol.
Definition
Let p be an odd prime numberPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. An integer a is a quadratic residue modulo p if it is congruent
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
to a perfect square
Square number
In mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...
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
Euler's criterion
In mathematics, Euler's criterion is used in determining in number theory whether a given integer is a quadratic residue modulo a prime.-Definition:Euler's criterion states:Let p be an odd prime and a an integer coprime to p. Then...
, 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
Carl Friedrich Gauss
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...
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
Periodic sequence
In mathematics, a periodic sequence is a sequence for which the same terms are repeated over and over:The number p of repeated terms is called the period.-Definition:A periodic sequence is a sequence a1, a2, a3, ... satisfying...
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}.
Properties of the Legendre symbol
There are a number of useful properties of the Legendre symbol which, together with the law of quadratic reciprocityQuadratic reciprocity
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic which gives conditions for the solvability of quadratic equations modulo prime numbers...
, 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 functionCompletely multiplicative functionIn number theory, functions of positive integers which respect products are important and are called completely multiplicative functions or totally multiplicative functions. Especially in number theory, a weaker condition is also important, respecting only products of coprime numbers, and such...
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
is the unique quadratic (or order 2) Dirichlet characterDirichlet characterIn number theory, Dirichlet characters are certain arithmetic functions which arise from completely multiplicative characters on the units of \mathbb Z / k \mathbb Z...
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
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 If p is a prime number then
For example,
This result comes from the theory of Lucas sequenceLucas sequenceIn mathematics, the Lucas sequences Un and Vn are certain integer sequences that satisfy the recurrence relationwhere P and Q are fixed integers...
s, which are used in primality testing. See Wall–Sun–Sun prime.
Legendre symbol and quadratic reciprocity
Let p and q be odd primes. Using the Legendre symbol, the quadratic reciprocityQuadratic reciprocityIn number theory, the law of quadratic reciprocity is a theorem about modular arithmetic which gives conditions for the solvability of quadratic equations modulo prime numbers...
law can be stated concisely:
-
Many proofs of quadratic reciprocityProofs of quadratic reciprocityIn number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusual number of proofs. Several hundred proofs of the law of quadratic reciprocity have been found.-Proofs that are accessible:...
are based on Legendre's formula
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 sumQuadratic Gauss sumIn number theory, quadratic Gauss sums are certain finite sums of roots of unity. A quadratic Gauss sum can be interpreted as a linear combination of the values of the complex exponential function with coefficients given by a quadratic character; for a general character, one obtains a more general...
and used the formula
-
- in his fourth and sixth proofs of quadratic reciprocity.
- Kronecker'sLeopold KroneckerLeopold Kronecker was a German mathematician who worked on number theory and algebra.He criticized Cantor's work on set theory, and was quoted by as having said, "God made integers; all else is the work of man"...
proof first establishes that
-
- Reversing the roles of p and q, he obtains the relation between
and 
- One of Eisenstein's proofs begins by showing that
-
- Using certain elliptic functionElliptic functionIn complex analysis, an elliptic function is a function defined on the complex plane that is periodic in two directions and at the same time is meromorphic...
s instead of the sine function, Eisenstein was able to prove cubicCubic reciprocityCubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x3 ≡ p is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the...
and quarticQuartic reciprocityQuartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x4 ≡ p is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the...
reciprocity as well.
Related functions
- The Jacobi symbolJacobi symbolThe Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in...
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 symbolKronecker symbolIn number theory, the Kronecker symbol, written as \left or , is a generalization of the Jacobi symbol to all integers n. It was introduced by Leopold Kronecker.-Definition:...
, in which the bottom argument may be any integer.
Computational example
The above properties, including the law of quadratic reciprocity, can be used to evaluate any Legendre symbol. For example:
Or using a more efficient computation:
The article Jacobi symbol has more examples of Legendre symbol manipulation.- Using certain elliptic function
- Reversing the roles of p and q, he obtains the relation between
- Gauss introduced the quadratic Gauss sum
- Special formulas for the Legendre symbol
- When viewed as a function of a, the Legendre symbol
- The Legendre symbol is a completely multiplicative function