Legendre symbol

From Wikipedia, the free encyclopedia

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[5]

Contents

[edit] 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.

[edit] Formulas for the Legendre symbol

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

\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.

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[7] that if \zeta = e^\frac{2\pi 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[8] and sixth[9], and for many[10] subsequent, proofs of quadratic reciprocity. See Gauss sum.

Kronecker's proof[11] 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[12] 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 elliptic functions instead of the sine, he was able to prove cubic and quartic reciprocity as well.

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

For example,

(\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.

This result comes from the theory of Lucas sequences, which are used in primality testing.[13] See Wall-Sun-Sun prime.

[edit] 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:

  1. \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.)
  1. If a ≡ b (mod p), then \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)
  1. \left(\frac{a^2}{p}\right) = 1
  1. \left(\frac{-1}{p}\right) = (-1)^{(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.

  1. \left(\frac{2}{p}\right) = (-1)^{(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

  1. If p and q are odd primes then \left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-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:

  1. For an odd prime p, \left(\frac{3}{p}\right) = (-1)^\left \lceil \frac{p+1}{6} \right \rceil =\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}
  1. For an odd prime p, \left(\frac{5}{p}\right) =(-1)^\left \lfloor \frac{p-2}{5} \right \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

  1. For an odd prime p, \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).

[edit] 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.

[edit] 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.

[edit] Notes

  1. ^ A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186
  2. ^ Which he named.
  3. ^ 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)
  4. ^ 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 ... "
  5. ^ From Z/pZ× to C2, which is the subgroup {-1,1} of C. (log and exp are older homomorphisms)
  6. ^ Lemmermeyer p. 8
  7. ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495. Crandall & Pomerance p. 92
  8. ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463-495
  9. ^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadritischen Resten" (1818) reprinted in Untersuchungen ... pp. 501-505
  10. ^ Scattered throughout the first 4 chapters of Lemmermeyer
  11. ^ Lemmermeyer, ex. p. 31, 1.34
  12. ^ Lemmermeyer, pp. 236 ff.
  13. ^ Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73-74.

[edit] References

  • Gauss, Carl Friedrich & Maser, H. (translator into German) (1965), Untersuchungen uber hohere 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 
  • Ireland, Kenneth & Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X 

[edit] External links