Legendre symbol explained

Legendre symbol
for various a (along top) and p (along left side). ! !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
301 −1
501 −1 −11
7011 −11 −1 −1
1101 −1111 −1 −1 −11 −1
Only 0 ≤ a < p are shown, since due to the first property below any other a can be reduced modulo p. Quadratic residues are highlighted in yellow, and correspond precisely to the values 0 and 1.

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

The Legendre symbol was introduced by Adrien-Marie Legendre in 1798[1] in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol and Dirichlet characters of higher order. The notational convenience of the Legendre symbol inspired introduction of several other "symbols" used in algebraic number theory, such as the Hilbert symbol and the Artin symbol.

Definition

Let

p

be an odd prime number. An integer

a

is a quadratic residue modulo

p

if it is congruent to a perfect square modulo

p

and is a quadratic nonresidue modulo

p

otherwise. The Legendre symbol is a function of

a

and

p

defined as
\left(a
p

\right)=\begin{cases} 1&ifaisaquadraticresiduemodulopanda\not\equiv0\pmodp,\\ -1&ifaisaquadraticnonresiduemodulop,\\ 0&ifa\equiv0\pmodp. \end{cases}

Legendre's original definition was by means of the explicit formula

\left(a
p

\right)\equiv

p-1
2
a

\pmodp   and   \left(

a
p

\right)\in\{-1,0,1\}.

By Euler's criterion, which had been discovered earlier and was known to Legendre, these two definitions are equivalent.[2] Thus Legendre's contribution lay in introducing a convenient notation that recorded quadratic residuosity of a mod p. For the sake of comparison, Gauss used the notation aRp, aNp according to whether a is a residue or a non-residue modulo p. For typographical convenience, the Legendre symbol is sometimes written as (a | p) or (a/p). For fixed p, the sequence

\left(\tfrac{0}{p}\right),\left(\tfrac{1}{p}\right),\left(\tfrac{2}{p}\right),\ldots

is periodic with period p and is sometimes called the Legendre sequence. Each row in the following table exhibits periodicity, just as described.

Table of values

The following is a table of values of Legendre symbol

\left(a
p

\right)

with p ≤ 127, a ≤ 30, p odd prime.
123456789101112131415161718192021222324252627282930
31−101−101−101−101−101−101−101−101−101−10
51−1−1101−1−1101−1−1101−1−1101−1−1101−1−110
711−11−1−1011−11−1−1011−11−1−1011−11−1−1011
111−1111−1−1−11−101−1111−1−1−11−101−1111−1−1−1
131−111−1−1−1−111−1101−111−1−1−1−111−1101−111
1711−11−1−1−111−1−1−11−111011−11−1−1−111−1−1−11
191−1−11111−11−11−1−1−1−111−101−1−11111−11−11
231111−11−111−1−111−1−11−11−1−1−1−101111−11−1
291−1−11111−11−1−1−11−1−11−1−1−11−11111−1−1101
3111−111−11111−1−1−11−11−1111−1−1−1−11−1−11−1−1
371−111−1−11−11111−1−1−11−1−1−1−11−1−1−11111−11
4111−111−1−1111−1−1−1−1−11−11−111−11−11−1−1−1−1−1
431−1−11−11−1−1111−111111−1−1−11−1111−1−1−1−1−1
471111−11111−1−11−11−1111−1−11−1−111−111−1−1
531−1−11−111−1111−11−1111−1−1−1−1−1−111−1−111−1
591−1111−11−11−1−11−1−1111−11111−1−111111−1
611−1111−1−1−11−1−111111−1−111−11−1−11−11−1−1−1
671−1−11−11−1−111−1−1−11111−11−1111111−1−11−1
71111111−1111−11−1−111−1111−1−1−111−11−111
731111−11−111−1−11−1−1−11−111−1−1−1111−11−1−1−1
7911−111−1−11111−11−1−11−1111111−111−1−1−1−1
831−111−1−11−11111−1−1−111−1−1−11−11−1111111
8911−111−1−11111−1−1−1−1111−1111−1−11−1−1−1−1−1
971111−11−111−111−1−1−11−11−1−1−11−111−11−1−1−1
1011−1−1111−1−11−1−1−111−111−11111111−1−1−1−11
10311−11−1−1111−1−1−11111111−1−1−11−111−1111
1071−111−1−1−1−1111111−11−1−11−1−1−11−11−11−111
1091−1111−11−11−1−11−1−111−1−1−1111−1−111111−1
11311−11−1−1111−11−11111−11−1−1−11−1−111−11−11
12711−11−1−1−111−11−11−111111−111−1−111−1−1−11

Properties of the Legendre symbol

There are a number of useful properties of the Legendre symbol which, together with the law of quadratic reciprocity, can be used to compute it efficiently.

g\in

*
F
p
, if

x=gr

, then

x

is a quadratic residue if and only if

r

is even. This shows that half of the elements in
*
F
p
are quadratic residues.

p\equiv3mod4

then the fact that
p+1
4

+

p+1
4

=

p+1
2

=

(p-1)+2
2

=

p-1
2

+1

gives us that

a=x(p+1)/4

is a square root of the quadratic residue

x

.
\left(a
p

\right)=\left(

b
p

\right).

\left(ab
p

\right)=\left(

a\right)\left(
p
b
p

\right).

\left(x2
p

\right)=\begin{cases}1&ifp\nmidx\ 0&ifp\midx.\end{cases}

\left(a
p

\right)

is the unique quadratic (or order 2) Dirichlet character modulo p.
\left(-1
p

\right)=

p-1
2
(-1)

= \begin{cases} 1&ifp\equiv1\pmod{4}\\ -1&ifp\equiv3\pmod{4}.\end{cases}

\left(2
p

\right)=(-1)\tfrac{p2-1}{8}= \begin{cases} 1&ifp\equiv1or7\pmod{8}\\ -1&ifp\equiv3or5\pmod{8}. \end{cases}

\left(a
p

\right)

for small values of a:
\left(3
p

\right)=

\lfloor
p+1
6
\rfloor
(-1)

= \begin{cases} 1&ifp\equiv1or11\pmod{12}\\ -1&ifp\equiv5or7\pmod{12}. \end{cases}

\left(5
p

\right)

\lfloor
2p+2
5
\rfloor
=(-1)

= \begin{cases} 1&ifp\equiv1or4\pmod5\\ -1&ifp\equiv2or3\pmod5. \end{cases}

F
p-\left(p\right)
5

\equiv0\pmodp,    Fp\equiv\left(

p
5

\right)\pmodp.

For example,

\begin{align} \left(\tfrac{2}{5}\right)&=-1,&F3&=2,&F2&=1,\  \left(\tfrac{3}{5}\right)&=-1,&F4&=3,&F3&=2,\  \left(\tfrac{5}{5}\right)&=0,&F5&=5,&&\  \left(\tfrac{7}{5}\right)&=-1,&F8&=21,&F7&=13,\  \left(\tfrac{11}{5}\right)&=1,&F10&=55,&F11&=89. \end{align}

Legendre symbol and quadratic reciprocity

Let p and q be distinct odd primes. Using the Legendre symbol, the quadratic reciprocity law can be stated concisely:

\left(q\right)\left(
p
p
q

\right)=(-1)\tfrac{p-1{2} ⋅ \tfrac{q-1}{2}}.

Many proofs of quadratic reciprocity are based on Euler's criterion

\left(a
p

\right)\equiva\tfrac{p-1{2}}\pmodp.

In addition, several alternative expressions for the Legendre symbol were devised in order to produce various proofs of the quadratic reciprocity law.

p-1
\sum
k=0
ak2
\zeta=\left(
a
p
p-1
\right)\sum
k=0
k2
\zeta

,    \zeta=

2\pii
p
e

in his fourth[4] and sixth[5] proofs of quadratic reciprocity.

\left(p
q

\right)

q-1
2
=sgn\left(\prod
i=1
p-1
2
\prod\left(
k=1
k-
p
i
q

\right)\right).

Reversing the roles of p and q, he obtains the relation between and .

\left(q
p

\right)

p-1
2
=\prod
n=1
\sin\left(2\piqn\right)
p
\sin\left(2\pin\right)
p

.

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

Related functions

Computational example

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

\begin{align} \left(

12345
331

\right)&=\left(

3
331

\right)\left(

5
331

\right)\left(

823
331

\right)\\ &=\left(

3
331

\right)\left(

5
331

\right)\left(

161
331

\right)\\ &=\left(

3
331

\right)\left(

5
331

\right)\left(

7
331

\right)\left(

23
331

\right)\\ &=(-1)\left(

331
3

\right)\left(

331
5

\right)(-1)\left(

331
7

\right)(-1)\left(

331
23

\right)\\ &=-\left(

1
3

\right)\left(

1
5

\right)\left(

2
7

\right)\left(

9
23

\right)\\ &=-\left(

1
3

\right)\left(

1
5

\right)\left(

2
7

\right)\left(

32
23

\right)\\ &=-(1)(1)(1)(1)\\ &=-1. \end{align}

Or using a more efficient computation:

\left(

12345
331

\right)=\left(

98
331

\right)=\left(

2 ⋅ 72
331

\right)=\left(

2
331

\right)=(-1)\tfrac{3312-1}{8}=-1.

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

Since no efficient factorization algorithm is known, but efficient modular exponentiation algorithms are, in general it is more efficient to use Legendre's original definition, e.g.

\begin{align} \left(98
331

\right)&\equiv

331-1
2
98

&\pmod{331}\\ &\equiv98165&\pmod{331}\\ &\equiv98 ⋅ (982)82&\pmod{331}\\ &\equiv98 ⋅ 582&\pmod{331}\\ &\equiv98 ⋅ 2541&\pmod{331}\\ &\equiv133 ⋅ 2540&\pmod{331}\\ &\equiv133 ⋅ 29420&\pmod{331}\\ &\equiv133 ⋅ 4510&\pmod{331}\\ &\equiv133 ⋅ 395&\pmod{331}\\ &\equiv222 ⋅ 394&\pmod{331}\\ &\equiv222 ⋅ 1972&\pmod{331}\\ &\equiv222 ⋅ 82&\pmod{331}\\ &\equiv-1&\pmod{331} \end{align}

using repeated squaring modulo 331, reducing every value using the modulus after every operation to avoid computation with large integers.

External links

Notes and References

  1. Book: Legendre, A. M. . Essai sur la théorie des nombres. Paris . 1798 . 186 .
  2. Hardy & Wright, Thm. 83.
  3. Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74.
  4. Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463–495
  5. Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reprinted in Untersuchungen ... pp. 501–505
  6. Lemmermeyer, ex. p. 31, 1.34
  7. Lemmermeyer, pp. 236 ff.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Legendre symbol".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2025, A B Cryer, All Rights Reserved. Cookie policy.