The Legendre symbol or quadratic character is a function introduced by Adrien-Marie Legendre in 1798 during his partly successful attempt to prove the law of quadratic reciprocity.. The symbol has served as the prototype for innumerable 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.

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 (assuming the gcd of a and p is 1):

$$

left(frac{a}{p}right) = begin{cases} ;;,0mbox{ if } a equiv 0 pmod{p} +1mbox{ if }a notequiv 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.

Formulas for the Legendre symbol

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

$$

left(frac{a}{p}right) =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 that if $zeta\; =\; e^frac\{2pi\; 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 and sixth, and for many subsequent, proofs of quadratic reciprocity. See Gauss sum.

Kronecker's proof is to establish that

$$

left(frac{p}{q}right)

sgnprod_{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 begins by showing

$$

left(frac{q}{p}right)

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}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. 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:

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} +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.

1. $$

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

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} +1mbox{ if }p equiv 1mbox{ or }11 pmod{12} -1mbox{ if }p equiv 5mbox{ 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} +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

1. For an odd prime p, $$

left(frac{7}{p}right) =begin{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\}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\; (1right\; )\; left\; (1right\; )\; left\; (1right\; )\; left\; (1right\; )\; =\; -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

External links

• Jacobi symbol calculator