World Library  
Flag as Inappropriate
Email this Article

Legendre symbol

Article Id: WHEBN0000018567
Reproduction Date:

Title: Legendre symbol  
Author: World Heritage Encyclopedia
Language: English
Subject: Jacobi symbol, Modular arithmetic, Adrien-Marie Legendre, Fibonacci number, Fekete polynomial
Publisher: World Heritage Encyclopedia

Legendre symbol

p \ a 0 1 2 3 4 5 6 7 8 9 10
3 0 1 -1
5 0 1 -1 -1 1
7 0 1 1 -1 1 -1 -1
11 0 1 -1 1 1 1 -1 -1 -1 1 -1

Legendre symbol (a/p) for various a (along top) and p (along left side). 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 a prime number p: its value on a (nonzero) quadratic residue mod p is 1 and on a non-quadratic residue (non-residue) is −1. Its value on 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 1
  • Properties of the Legendre symbol 2
  • Legendre symbol and quadratic reciprocity 3
  • Related functions 4
  • Computational example 5
  • Notes 6
  • References 7
  • External links 8


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

\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{ if } a \text{ is a quadratic residue modulo } p \text{ and } a \not\equiv 0\pmod{p} \\ -1 & \text{ if } a \text{ is a quadratic non-residue modulo } p \\ 0 & \text{ if } a \equiv 0 \pmod{p}. \end{cases}

Legendre's original definition was by means of an explicit formula:

\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \quad \text{ and } \quad\left(\frac{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 a\mathrm{R}p, a\mathrm{N}p 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). The sequence (a|p) for a equal to 0,1,2,... is periodic with period p and is sometimes called the Legendre sequence, with {0,1,−1} values occasionally replaced by {1,0,1} or {0,1,0}.[3]

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.

  • The Legendre symbol is periodic in its first (or top) argument: if ab (mod p), then
    \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right).
  • The Legendre symbol is a completely multiplicative function of its top argument:
    \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).
  • In particular, the product of two numbers that are both quadratic residues or quadratic non-residues modulo p is a residue, whereas the product of a residue with a non-residue is a non-residue. A special case is the Legendre symbol of a square:
    \left(\frac{x^2}{p}\right) = \begin{cases} 1 & \mbox{if }p\nmid x\\ 0 & \mbox{if }p\mid x. \end{cases}
  • When viewed as a function of a, the Legendre symbol \left(\frac{a}{p}\right) is the unique quadratic (or order 2) Dirichlet character modulo p.
  • The first supplement to the law of quadratic reciprocity:
    \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} =\begin{cases} 1 & \mbox{ if }p \equiv 1\pmod{4} \\ -1 & \mbox{ if }p \equiv 3\pmod{4}. \end{cases}
  • The second 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}
  • Special formulas for the Legendre symbol \left(\frac{a}{p}\right) for 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}
  • 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, \qquad 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.[4] See Wall–Sun–Sun prime.

Legendre symbol and quadratic reciprocity

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

\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right) (-1)^{\tfrac{p-1}{2}\tfrac{q-1}{2}}.

Many proofs of quadratic reciprocity are based on Legendre's formula

\left(\frac{a}{p}\right) \equiv a^{\tfrac{p-1}{2}} \pmod p.

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

\sum_{k=0}^{p-1}\zeta^{ak^2}=\left(\frac{a}{p}\right)\sum_{k=0}^{p-1}\zeta^{k^2},\qquad \zeta = e^{\frac{2\pi i}{p}}
in his fourth[5] and sixth[6] proofs of quadratic reciprocity.
\left(\frac{p}{q}\right) =\sgn\left(\prod_{i=1}^{\frac{q-1}{2}}\prod_{k=1}^{\frac{p-1}{2}}\left(\frac{k}{p}-\frac{i}{q}\right)\right).
Reversing the roles of p and q, he obtains the relation between \left(\frac{p}{q}\right) and \left(\frac{q}{p}\right).
  • One of Eisenstein's proofs[8] begins by showing that
\left(\frac{q}{p}\right) =\prod_{n=1}^{\frac{p-1}{2}} \frac{\sin\left(\frac{2\pi qn}{p}\right)}{\sin\left(\frac{2\pi n}{p}\right)}.
Using certain elliptic functions instead of the sine function, Eisenstein was able to prove cubic and quartic reciprocity as well.

Related functions

  • The Jacobi symbol \left(\frac{a}{n}\right) is a generalization of the Legendre symbol that allows for a composite second (bottom) argument n, although n must still be odd and positive. This generalization provides an efficient way to compute all Legendre symbols without performing factorization along the way.
  • A further extension is the Kronecker symbol, in which the bottom argument may be any integer.
  • The power residue symbol \left(\tfrac{a}{p}\right)_n generalizes the Legendre symbol to higher power n. The Legendre symbol represents the power residue symbol for n = 2.

Computational example

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

\begin{align} \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^2}{23}\right )\\ &= -(1) (1) (1) (1) \\ &= -1. \end{align}

Or using a more efficient computation:

\left ( \frac{12345}{331}\right )=\left ( \frac{98}{331}\right )=\left ( \frac{2 \cdot 7^2}{331}\right )=\left ( \frac{2}{331}\right )=(-1)^\tfrac{331^2-1}{8}=-1.

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


  1. ^ A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186
  2. ^ Hardy & Wright, Thm. 83.
  3. ^ Jeong-Heon Kim and Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).
  4. ^ Ribenboim, p. 64; Lemmermeyer, ex 2.25-2.28, pp. 73–74.
  5. ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463–495
  6. ^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reprinted in Untersuchungen ... pp. 501–505
  7. ^ Lemmermeyer, ex. p. 31, 1.34
  8. ^ Lemmermeyer, pp. 236 ff.


  • 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,  
  • Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithmeticae (Second, corrected edition), New York:  
  • Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge:  
  • Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York:  
  • Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin:  
  • Ribenboim, Paulo (1996), The New Book of Prime Number Records, New York:  

External links

  • Jacobi symbol calculator
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.