Legendre symbol: Definition from Answers.com

The Legendre symbol or quadratic character is a function introduced by Adrien-Marie Legendre in 1798^[1] during his partly successful attempt to prove the law of quadratic reciprocity.^[2]^[3]. The symbol has served as the prototype for innumerable^[4] 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.^{[citation needed]}^[5]

1 Definition
2 Formulas for the Legendre symbol
- 2.1 Other formulas involving the Legendre symbol
3 Properties of the Legendre symbol
4 Computational example
5 Related functions
6 Notes
7 References
8 External links

Definition

The Legendre symbol $(\tfrac{a}{p})$ (sometimes written (a|p) for typographical convenience) is defined for integers a and positive odd primes p by:

$\left(\frac{a}{p}\right) = \begin{cases} \;\;\,0\mbox{ if } a \equiv 0 \pmod{p} \\+1\mbox{ if }a \not\equiv 0\pmod{p} \mbox{ and for some integer }x, x^2\equiv \;a \pmod{p} \\-1\mbox{ 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.

Gauss used the notation $a R p$ , $a N p$ according as a is a residue or a non-residue of p.

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.^[6]

Formulas for the Legendre symbol

Legendre originally defined his symbol (for a relatively prime to p) as^[7]

$\left(\frac{a}{p}\right) =\pm1\equiv 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.^[8]

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^[9] that if $ζ = e 2π i / p$ then

$\left(\frac{a}{p}\right) =\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^[10] and sixth^[11], and for many^[12] subsequent, proofs of quadratic reciprocity. See Gauss sum.

Kronecker's proof^[13] is to establish that

$\left(\frac{p}{q}\right) =\sgn\prod_{i=1}^{\frac{q-1}{2}}\prod_{k=1}^{\frac{p-1}{2}}\left(\frac{k}{p}-\frac{i}{q}\right)$

and then switch p and q.

One of Eisenstein's proofs^[14] begins by showing

$\left(\frac{q}{p}\right) =\prod_{n=1}^{\frac{p-1}{2}} \frac{\sin (\frac{2\pi}{p}qn)}{\sin(\frac{2\pi}{p}n)}.$

Using certain 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}\right)} \equiv 0 \pmod p,\;\;\; F_{p} \equiv \left(\frac{p}{5}\right) \pmod p.$

For example,

$\begin{align} &(\tfrac{2}{5}) &= &-1, &F_3 &= 2, \;\;\;\;&F_2 &=1,\\ &(\tfrac{3}{5}) &= &-1, &F_4 &= 3,&F_3&=2,\\ &(\tfrac{5}{5}) &= &\;\;\;\;0, &F_5 &= 5,\\ &(\tfrac{7}{5}) &= &-1, &F_8 &= 21,&F_7&=13,\\ &(\tfrac{11}{5}) &= &+1, &F_{10} &= 55, &F_{11}&=89. \end{align}$

This result comes from the theory of Lucas sequences, which are used in primality testing.^[15] 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}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ (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}\right) = \left(\frac{b}{p}\right)$

$\left(\frac{a^2}{p}\right) = \begin{cases} 1&\mbox{if }p\nmid a\\0&\mbox{if }p\mid a \end{cases}$

$\left(\frac{-1}{p}\right) = (-1)^\tfrac{p-1}{2} =\begin{cases} +1\mbox{ if }p \equiv 1\pmod{4} \\ -1\mbox{ if }p \equiv 3\pmod{4} \end{cases}$

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

$\left(\frac{2}{p}\right) = (-1)^\tfrac{p^2-1}{8} =\begin{cases} +1\mbox{ if }p \equiv 1\mbox{ or }7 \pmod{8} \\ -1\mbox{ if }p \equiv 3\mbox{ 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}\right) = \left(\frac{p}{q}\right)(-1)^{\tfrac{p-1}{2}\tfrac{q-1}{2}}.$

See the articles quadratic reciprocity and proofs of quadratic reciprocity.

There are special formulas for the Legendre symbol (a|p) for some small values of a:

For an odd prime p ≠ 3, $\left(\frac{3}{p}\right) = (-1)^{\big\lfloor \frac{p+1}{6}\big\rfloor} =\begin{cases} +1\mbox{ if }p \equiv 1\mbox{ or }11 \pmod{12} \\ -1\mbox{ if }p \equiv 5\mbox{ or }7 \pmod{12} \end{cases}$

For an odd prime p ≠ 5, $\left(\frac{5}{p}\right) =(-1)^{\big\lfloor \frac{p+2}{5}\big \rfloor} =\begin{cases} +1\mbox{ if }p \equiv 1\mbox{ or }4 \pmod5 \\ -1\mbox{ if }p \equiv 2\mbox{ or }3 \pmod5 \end{cases},$

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

For an odd prime p ≠ 7, $\left(\frac{7}{p}\right) =\begin{cases} +1\mbox{ if }p \equiv 1, 3, 9, 19, 25,\mbox{ or }27\pmod{28} \\ -1\mbox{ 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}\right )$

$=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{823}{331}\right )$

$=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{161}{331}\right )$

$=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{7}{331}\right ) \left ( \frac{23}{331}\right )$

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

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

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

$= - \left (1\right ) \left (1\right ) \left (1\right ) \left (1\right ) = -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

^ A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186
^ 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)
^ 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 ... "
^ From Z/pZ^× to C₂, which is the subgroup {-1,1} of C. (log and exp are older homomorphisms)
^ Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).
^ Lemmermeyer p. 8
^ Hardy & Wright, Thm. 83. See Wilson's theorem.
^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495. Crandall & Pomerance p. 92
^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495
^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in Untersuchungen ... pp. 501-505
^ Scattered throughout the first 4 chapters of Lemmermeyer
^ Lemmermeyer, ex. p. 31, 1.34
^ Lemmermeyer, pp. 236 ff.
^ Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73-74.

References

Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8

Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithmeticae (Second, corrected edition), New York: Springer, ISBN 0387962549

Bach, Eric; Shallit, Jeffrey (1966), Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, ISBN 0-262-02045-5

Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0198531715

Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X

Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66967-4

Ribenboim, Paulo (1996), The New Book of Prime Number Records, New York: Springer, ISBN 0-387-94457-5

External links

Jacobi symbol calculator

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Are there any books written about Gertrude Sanford Legendre? Read answer...
	What are the Legendre's in Pokemon heart gold and soul silver? Read answer...
	How do you get the legendre pokemon if it runs away in pokemon sapphire? Read answer...

	How much legendre's pokemon are off ruby?
	What is the nationality of sister marthe de stpaul legendre?
	What legendre's can you get in fire red no event or hack?

		Sci-Tech Dictionary. McGraw-Hill Dictionary of Scientific and Technical Terms. Copyright © 2003, 1994, 1989, 1984, 1978, 1976, 1974 by McGraw-Hill Companies, Inc. All rights reserved. Read more
		Wikipedia. This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Legendre symbol". Read more

Legendre symbol

Contents