Legendre symbol

The Legendre symbol or quadratic character is a function introduced by Adrien-Marie Legendre in 1798 [A. M. Legendre "Essai sur la theorie des nombres" Paris 1798, p 186] during his partly successful attempt to prove the law of quadratic reciprocity. [Which he named.] [Stated in posthumous paper by Euler (1783), and by Legendre in 1786. First proved by Gauss in 1796, published in DA (1801); arts. 107-144 (first proof), arts 253-262 (second proof)] . The symbol has served as the prototype for innumerable [Lemmermeyer, p.xiv "even in a case as simple as biquadratic reciprocity we have to distinguish four different symbols, namely the quadratic and biquadratic residue symbols in Z [i] , the Legendre symbol in Z, and the rational quartic residue symbol in Z ... "] higher power residue symbols; other extensions and generalizations include the Jacobi symbol, the Kronecker symbol, the Hilbert symbol and the Artin symbol. It is one of the earliest examples of a homomorphism. [From Z/pZ^× to C₂, which is the subgroup {-1,1} of C. (log and exp are older homomorphisms)]

Definition

The Legendre symbol $(\; frac\{a\}\{p\})$ (sometimes written ("a"|"p") for typographical convenience) is defined for integers "a" and positive odd primes "p" by (assuming the gcd of a and p is 1):

:

If ("a"|"p") = 1, "a" is called a quadratic residue (mod "p"); if ("a"|"p") = −1, "a" is called a quadratic nonresidue (mod p).
It is usual to treat zero as a special case.

The periodic sequence ("a"|"p") for "a" equal to 0,1,2,... is sometimes called the Legendre sequence, sometimes with {0,1,-1} values replaced by {1,0,1} or {0,1,0}, respectively.Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," "Designs, Codes, and Cryptography" 24, p. 343–348 (2001).]

Formulas for the Legendre symbol

Legendre originally "defined" his symbol (for "a" relatively prime to "p") as [Lemmermeyer p. 8]

:$left(frac\{a\}\{p\}\; ight)\; =pm1equiv\; a^\{(p-1)/2\}pmod\; p.$

Euler had earlier proved that this expression is ≡ 1 (mod "p") if "a" is a quadratic residue (mod "p") and that it is ≡ −1 if "a" is a quadratic nonresidue; this equivalence is now known as Euler's criterion.

In addition to this fundamental formula, there are many other expressions for ("a"|"p"), most of which are used in proofs of quadratic reciprocity.

Gauss proved [Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in "Untersuchungen ..." pp. 463-495. Crandall & Pomerance p. 92] that if $zeta\; =\; e^frac\{2pi\; i\}\{p\}$ then

:$left(frac\{a\}\{p\}\; ight)$

=frac{1+zeta^{a}+zeta^{4a}+zeta^{9a}+dots+zeta^{(p-1)^2a{1+zeta+zeta^{4}+zeta^{9}+dots+zeta^{(p-1)^2

=frac{2(1+zeta^{a}+zeta^{4a}+zeta^{9a}+dots+zeta^{(p-1)^2a})}{sqrt p(1+i)(1+(-i)^p)}.

This is the basis for his fourth [Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in "Untersuchungen ..." pp. 463-495] and sixth [Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in "Untersuchungen ..." pp. 501-505] , and for many [Scattered throughout the first 4 chapters of Lemmermeyer] subsequent, proofs of quadratic reciprocity. See Gauss sum.

Kronecker's proof [Lemmermeyer, ex. p. 31, 1.34] is to establish that:$left(frac\{p\}\{q\}\; ight)=sgnprod\_\{i=1\}^\{frac\{q-1\}\{2prod\_\{k=1\}^\{frac\{p-1\}\{2left(frac\{k\}\{p\}-frac\{i\}\{q\}\; ight)$and then switch "p" and "q".

One of Eisenstein's proofs [Lemmermeyer, pp. 236 ff.] begins by showing:$left(frac\{q\}\{p\}\; ight)=prod\_\{n=1\}^\{frac\{p-1\}\{2\; frac\{sin\; (frac\{2pi\}\{p\}qn)\}\{sin(frac\{2pi\}\{p\}n)\}.$

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

Other formulas involving the Legendre symbol

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

:$F\_\{p-left(frac\{p\}\{5\}\; ight)\}\; equiv\; 0\; pmod\; p,;;;F\_\{p\}\; equiv\; left(frac\{p\}\{5\}\; ight)\; pmod\; p.$

For example,

:$(\; frac\{2\}\{5\})\; =\; -1,\; ,,\; F\_3\; =\; 2,\; F\_2=1,$ :$(\; frac\{3\}\{5\})\; =\; -1,\; ,,\; F\_4\; =\; 3,F\_3=2,$ :$(\; frac\{5\}\{5\})\; =\; ;;,0,,,\; F\_5\; =\; 5,$ :$(\; frac\{7\}\{5\})\; =\; -1,\; ,,F\_8\; =\; 21,;;F\_7=13,$ :$(\; frac\{11\}\{5\})\; =\; +1,\; F\_\{10\}\; =\; 55,\; F\_\{11\}=89.$

This result comes from the theory of Lucas sequences, which are used in primality testing. [Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73-74.] See Wall-Sun-Sun prime.

Properties of the Legendre symbol

There are a number of useful properties of the Legendre symbol which can be used to speed up calculations. They include:

#$left(frac\{ab\}\{p\}\; ight)\; =\; left(frac\{a\}\{p\}\; ight)left(frac\{b\}\{p\}\; ight)$ (It is a completely multiplicative function in its top argument. This property can be understood to mean: the product of two residues or non-residues is a residue, whereas the product of a residue with a non-residue is a non-residue.)

#If "a" ≡ "b" (mod "p"), then $left(frac\{a\}\{p\}\; ight)\; =\; left(frac\{b\}\{p\}\; ight)$

#$left(frac\{a^2\}\{p\}\; ight)\; =\; 1$

#

This is called the first supplement to the law of quadratic reciprocity.

#

This is called the second supplement to the law of quadratic reciprocity. The general law of quadratic reciprocity is

#If "p" and "q" are odd primes then $left(frac\{q\}\{p\}\; ight)\; =\; left(frac\{p\}\{q\}\; ight)(-1)^\{\; frac\{p-1\}\{2\}\; frac\{q-1\}\{2\}\; \}.$

See the articles quadratic reciprocity and proofs of quadratic reciprocity.

There are special formulas for some small values of "p":

#For an odd prime "p",

#For an odd prime "p",

but in general it is simpler to list the residues and non-residues

#For an odd prime "p",

The Legendre symbol ("a"|"p") is a Dirichlet character (mod "p").

Computational example

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

:$left\; (\; frac\{12345\}\{331\}\; ight\; )$

:$=left\; (\; frac\{3\}\{331\}\; ight\; )\; left\; (\; frac\{5\}\{331\}\; ight\; )\; left\; (\; frac\{823\}\{331\}\; ight\; )$

:$=left\; (\; frac\{3\}\{331\}\; ight\; )\; left\; (\; frac\{5\}\{331\}\; ight\; )\; left\; (\; frac\{161\}\{331\}\; ight\; )$

:$=left\; (\; frac\{3\}\{331\}\; ight\; )\; left\; (\; frac\{5\}\{331\}\; ight\; )\; left\; (\; frac\{7\}\{331\}\; ight\; )\; left\; (\; frac\{23\}\{331\}\; ight\; )$

:$=\; (-1)\; left\; (\; frac\{331\}\{3\}\; ight\; )\; left\; (\; frac\{331\}\{5\}\; ight\; )\; (-1)\; left\; (\; frac\{331\}\{7\}\; ight\; )\; (-1)\; left\; (\; frac\{331\}\{23\}\; ight\; )$

:$=-left\; (\; frac\{1\}\{3\}\; ight\; )\; left\; (\; frac\{1\}\{5\}\; ight\; )\; left\; (\; frac\{2\}\{7\}\; ight\; )\; left\; (\; frac\{9\}\{23\}\; ight\; )$

:$=-left\; (\; frac\{1\}\{3\}\; ight\; )\; left\; (\; frac\{1\}\{5\}\; ight\; )\; left\; (\; frac\{2\}\{7\}\; ight\; )\; left\; (\; frac\{3\}\{23\}\; ight\; )^2$

:$=\; -\; left\; (1\; ight\; )\; left\; (1\; ight\; )\; left\; (1\; ight\; )\; left\; (1\; ight\; )\; =\; -1.$

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

Related functions

*The Jacobi symbol is a generalization of the Legendre symbol that allows composite bottom numbers, although the bottom number must still be odd and positive. This generalization provides an efficient way to compute all Legendre symbols.
*A further generalization is the Kronecker symbol, which extends the bottom numbers to all integers.

Notes

References

*citation
last1 = Gauss | first1 = Carl Friedrich
last2 = Maser | first2 = H. (translator into German)
title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition)
publisher = Chelsea
location = New York
date = 1965
isbn = 0-8284-0191-8

*citation
last1 = Gauss | first1 = Carl Friedrich
last2 = Clarke | first2 = Arthur A. (translator into English)
title = Disquisitiones Arithmeticae (Second, corrected edition)
publisher = Springer
location = New York
date = 1986
isbn = 0387962549

*citation
last1 = Bach | first1 = Eric
last2 = Shallit | first2 = Jeffrey
title = Algorithmic Number Theory (Vol I: Efficient Algorithms)
publisher = The MIT Press
location = Cambridge
date = 1966
isbn = 0-262-02045-5

*citation
last1 = Lemmermeyer | first1 = Franz
title = Reciprocity Laws: from Euler to Eisenstein
publisher = Springer
location = Berlin
date = 2000
isbn = 3-540-66967-4

*citation
last1 = Ireland | first1 = Kenneth
last2 = Rosen | first2 = Michael
title = A Classical Introduction to Modern Number Theory (Second edition)
publisher = Springer
location = New York
date = 1990
isbn = 0-387-97329-X

*citation
last1 = Ribenboim | first1 = Paulo
title = The New Book of Prime Number Records
publisher = Springer
location = New York
date = 1996
isbn = 0-387-94457-5

External links

* [http://www.math.fau.edu/richman/jacobi.htm Jacobi symbol calculator]