Legendre symbol

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 C2, which is the subgroup {-1,1} of C. (log and exp are older homomorphisms)]


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):

:left(frac{a}{p} ight) = egin{cases};;,0mbox{ if } a equiv 0 pmod{p}\+1mbox{ if }a otequiv 0pmod{p} mbox{ and for some integer }x, x^2equiv ;a pmod{p}\-1mbox{ if there is no such } x. end{cases}

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{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 F1 = F2 = 1, Fn+1 = Fn + Fn-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

#left(frac{-1}{p} ight) = (-1)^{(p-1)/2}=egin{cases}+1mbox{ if }p equiv 1pmod{4} \-1mbox{ if }p equiv 3pmod{4} end{cases}

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

#left(frac{2}{p} ight) = (-1)^{(p^2-1)/8}=egin{cases}+1mbox{ if }p equiv 1mbox{ or }7 pmod{8} \-1mbox{ if }p equiv 3mbox{ or }5 pmod{8} end{cases}

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", left(frac{3}{p} ight)= (-1)^left lceil frac{p+1}{6} ight ceil =egin{cases}+1mbox{ if }p equiv 1mbox{ or }11 pmod{12} \-1mbox{ if }p equiv 5mbox{ or }7 pmod{12} end{cases}

#For an odd prime "p", left(frac{5}{p} ight)=(-1)^left lfloor frac{p-2}{5} ight floor =egin{cases}+1mbox{ if }p equiv 1mbox{ or }4 pmod5 \-1mbox{ if }p equiv 2mbox{ or }3 pmod5 end{cases},

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

#For an odd prime "p", left(frac{7}{p} ight)=egin{cases}+1mbox{ if }p equiv 1, 3, 9, 19, 25,mbox{ or }27pmod{28} \-1mbox{ if }p equiv 5, 11, 13, 15, 17, mbox{ or } 23 pmod{28} end{cases}

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.



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

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

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

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

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

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]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Legendre-Symbol — Das Legendre Symbol ist eine Kurzschreibweise, die in der Zahlentheorie, einem Teilgebiet der Mathematik, verwendet wird. Es ist nach dem französischen Mathematiker Adrien Marie Legendre benannt und wird wie folgt notiert: Diese drei Notationen… …   Deutsch Wikipedia

  • Legendre symbol — noun Mathematical function of an integer and a prime, written , indicating whether a is a square modulo p …   Wiktionary

  • Jacobi symbol — The Jacobi symbol is a generalization of the Legendre symbol introduced by Jacobi in 1837 [C.G.J.Jacobi Uber die Kreisteilung und ihre Anwendung auf die Zahlentheorie , Bericht Ak. Wiss. Berlin (1837) pp 127 136] . It is of theoretical interest… …   Wikipedia

  • Jacobi-Symbol — Das Jacobi Symbol, benannt nach Carl Gustav Jacob Jacobi, ist eine Verallgemeinerung des Legendre Symbols. Das Jacobi Symbol kann wiederum zum Kronecker Symbol verallgemeinert werden. Die Notation ist die gleiche wie die des Legendre Symbols:… …   Deutsch Wikipedia

  • Adrien Marie Legendre — [ləˈʒɑ̃ːdrə] (* 18. September 1752 in Paris; † 10. Januar 1833 ebenda) war ein französischer Mathematiker. Inhaltsverzeichnis 1 Leben 2 Werk 3 Sonstiges …   Deutsch Wikipedia

  • Adrien-Marie Legendre — Infobox Scientist name = Adrien Marie Legendre caption = Adrien Marie Legendre birth date = birth date|1752|9|18|mf=y birth place = Paris, France death date = death date and age|1833|1|10|1752|9|18|mf=y death place = Paris, France residence =… …   Wikipedia

  • Adrien-Marie Legendre — Karikatur Legendres des französischen Künstlers Julien Leopold Boilly Adrien Marie Legendre [ləˈʒɑ̃ːdrə] (* 18. September 1752 in Paris; † 10. Januar 1833 ebenda) war ein französischer Mathematiker. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Kronecker symbol — Note: You might be looking for the Kronecker delta. In number theory, the Kronecker symbol is a generalization of the Jacobi symbol to all integers. Let n be an integer, with prime factorization :u cdot {p 1}^{e 1} cdots {p k}^{e k},where u is a… …   Wikipedia

  • 26950 Legendre — Infobox Planet minorplanet = yes width = 25em bgcolour = #FFFFC0 apsis = name = Legendre symbol = caption = discovery = yes discovery ref = discoverer = P. G. Comba discovery site = Prescott discovered = May 11, 1997 designations = yes mp name =… …   Wikipedia

  • Símbolo de Legendre — El símbolo de Legendre, , es una función multiplicativa utilizada en teoría de números que toma como argumentos un entero a y un primo p y devuelve uno de los valores 1, 1, ó 0 dependiendo de si a es o no residuo cuadrático módulo p, es decir de… …   Wikipedia Español