In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
, the Legendre symbol is a
multiplicative function
In number theory, a multiplicative function is an arithmetic function ''f''(''n'') of a positive integer ''n'' with the property that ''f''(1) = 1 and
f(ab) = f(a)f(b) whenever ''a'' and ''b'' are coprime.
An arithmetic function ''f''(''n'') is ...
with values 1, −1, 0 that is a quadratic character modulo an odd
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
''p'': its value at a (nonzero)
quadratic residue mod ''p'' is 1 and at a non-quadratic residue (''non-residue'') is −1. Its value at zero is 0.
The Legendre symbol was introduced by
Adrien-Marie Legendre
Adrien-Marie Legendre (; ; 18 September 1752 – 9 January 1833) was a French mathematician who made numerous contributions to mathematics. Well-known and important concepts such as the Legendre polynomials and Legendre transformation are named ...
in 1798 in the course of his attempts at proving the
law of quadratic reciprocity
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...
. Generalizations of the symbol include the
Jacobi symbol
Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
and
Dirichlet character
In analytic number theory and related branches of mathematics, a complex-valued arithmetic function \chi:\mathbb\rightarrow\mathbb is a Dirichlet character of modulus m (where m is a positive integer) if for all integers a and b:
:1) \chi ...
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 is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...
, such as the
Hilbert symbol In mathematics, the Hilbert symbol or norm-residue symbol is a function (–, –) from ''K''× × ''K''× to the group of ''n''th roots of unity in a local field ''K'' such as the fields of reals or p-adic numbers . It is related to reciprocity ...
and the
Artin symbol The Artin reciprocity law, which was established by Emil Artin in a series of papers (1924; 1927; 1930), is a general theorem in number theory that forms a central part of global class field theory. The term "reciprocity law" refers to a long line ...
.
Definition
Let
be an odd
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. An integer
is a
quadratic residue modulo
if it is
congruent
Congruence may refer to:
Mathematics
* Congruence (geometry), being the same size and shape
* Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure
* In mod ...
to a
perfect square modulo
and is a quadratic nonresidue modulo
otherwise. The Legendre symbol is a function of
and
defined as
:
Legendre's original definition was by means of the explicit formula
:
By
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then
:
a^ \equiv
\begin
\;\;\,1\pmod& \text ...
, 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
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
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
is
periodic with period ''p'' and is sometimes called the Legendre sequence. Each row in the following table exhibits periodicity, just as described.
Table of values
The following is a table of values of Legendre symbol
with ''p'' ≤ 127, ''a'' ≤ 30, ''p'' 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
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...
, can be used to compute it efficiently.
* Given a generator
, if
, then
is a quadratic residue if and only if
is even. This shows that half of the nonzero elements in
are quadratic residues.
* If
then the fact that
*:
gives us that
is the square root of the quadratic residue
.
* 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 In number theory, functions of positive integers which respect products are important and are called completely multiplicative functions or totally multiplicative functions. A weaker condition is also important, respecting only products of coprime ...
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 character
In analytic number theory and related branches of mathematics, a complex-valued arithmetic function \chi:\mathbb\rightarrow\mathbb is a Dirichlet character of modulus m (where m is a positive integer) if for all integers a and b:
:1) \chi ...
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
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
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 sequence
In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation
: x_n = P \cdot x_ - Q \cdot x_
where P and Q are fixed integers. Any sequence satisfying this recu ...
s, which are used in
primality testing
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wh ...
. See
Wall–Sun–Sun prime
In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.
Definition
Let p be a prime number. When each term in the sequence of Fibonac ...
.
Legendre symbol and quadratic reciprocity
Let ''p'' and ''q'' be distinct odd primes. Using the Legendre symbol, the
quadratic reciprocity
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...
law can be stated concisely:
:
Many
proofs of quadratic reciprocity are based on
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then
:
a^ \equiv
\begin
\;\;\,1\pmod& \text ...
:
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 In 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; fo ...
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 () and ().
* One of
Eisenstein's proofs
[Lemmermeyer, pp. 236 ff.] begins by showing that
::
: Using certain
elliptic function
In the mathematical field of complex analysis, elliptic functions are a special kind of meromorphic functions, that satisfy two periodicity conditions. They are named elliptic functions because they come from elliptic integrals. Originally those in ...
s instead of the
sine function, Eisenstein was able to prove
cubic and
quartic reciprocity
Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence ''x''4 ≡ ''p'' (mod ''q'') is solvable; the word "reciprocity" comes from the form o ...
as well.
Related functions
* The
Jacobi symbol
Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
() 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 number theory, the Kronecker symbol, written as \left(\frac an\right) or (a, n), is a generalization of the Jacobi symbol to all integers n. It was introduced by .
Definition
Let n be a non-zero integer, with prime factorization
:n=u \cdot ...
, in which the bottom argument may be any integer.
* The
power residue symbol
In algebraic number theory the ''n''-th power residue symbol (for an integer ''n'' > 2) is a generalization of the (quadratic) Legendre symbol to ''n''-th powers. These symbols are used in the statement and proof of cubic, quartic, Eisenstein ...
() generalizes the Legendre symbol to higher power ''n''. The Legendre symbol represents the
power residue symbol
In algebraic number theory the ''n''-th power residue symbol (for an integer ''n'' > 2) is a generalization of the (quadratic) Legendre symbol to ''n''-th powers. These symbols are used in the statement and proof of cubic, quartic, Eisenstein ...
for ''n'' = 2.
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
Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
has more examples of Legendre symbol manipulation.
Since no efficient
factorization
In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
algorithm is known, but efficient
modular exponentiation
Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys.
Modul ...
algorithms are, in general it is more efficient to use Legendre's original definition, e.g.
:
using
repeated squaring modulo 331, reducing every value using the modulus after every operation to avoid computation with large integers.
Notes
References
*
*
*
*
*
*
*{{citation
, last1 = Ribenboim , first1 = Paulo
, title = The New Book of Prime Number Records
, publisher =
Springer
Springer or springers may refer to:
Publishers
* Springer Science+Business Media, aka Springer International Publishing, a worldwide publishing group founded in 1842 in Germany formerly known as Springer-Verlag.
** Springer Nature, a multinationa ...
, location = New York
, year = 1996
, isbn = 0-387-94457-5
External links
Jacobi symbol calculator
Modular arithmetic
Quadratic residue