Surf Wiki
Save to docs
general/modular-arithmetic

From Surf Wiki (app.surf) — the open knowledge base

Legendre symbol

Function in number theory

Function in number theory

01234567891011123571113
01−1
01−1−11
011−11−1−1
01−1111−1−1−11−1
01−111−1−1−1−111−11

In number theory, the Legendre symbol is a function of a and p defined as :\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 nonresidue modulo } p, \ 0 & \text{if } a \equiv 0 \pmod p. \end{cases}

where p is an odd prime number and a is a positive integer that may or may not be a quadratic residue mod p. The Legendre symbol is a multiplicative function

The Legendre symbol was introduced by Adrien-Marie Legendre in 1797 or 1798 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

Legendre's original definition was by means of the 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. 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.

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.

  • Given a generator g \in \mathbb{F}_p^, if x = g^r, then x is a quadratic residue if and only if r is even. This shows that half of the elements in \mathbb{F}_p^ are quadratic residues.
  • If p \equiv 3 \text{ mod } 4 then the fact that
  • : \frac{p+1}{4} + \frac{p+1}{4} = \frac{p+1}2 = \frac{(p-1)+2}{2} = \frac{p-1}2 + 1 gives us that a = x^{(p+1)/4} is a square root of the quadratic residue x.
  • The Legendre symbol is periodic in its first (or top) argument: if a ≡ b (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{2p+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 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} \left(\tfrac{2}{5}\right) &= -1, & F_3 &= 2, & F_2 &= 1, \ \left(\tfrac{3}{5}\right) &= -1, & F_4 &= 3, & F_3 &= 2, \ \left(\tfrac{5}{5}\right) &= 0, & F_5 &= 5, & & \ \left(\tfrac{7}{5}\right) &= -1, & F_8 &= 21, & F_7 &= 13, \ \left(\tfrac{11}{5}\right) &= 1, & F_{10} &= 55, & F_{11} &= 89. \end{align}
  • This result comes from the theory of Lucas sequences, which are used in primality testing. See Wall–Sun–Sun prime.

Sums of Legendre symbols

Sums of the form \sum \left(\frac{f\left(a \right) }{p}\right), typically taken over all integers in the range \left[0,p-1\right] for some function f, are a special case of character sums. They are of interest in the distribution of quadratic residues modulo a prime number.

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

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

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

  • Gauss introduced the quadratic Gauss sum and used the formula

::\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 and sixth proofs of quadratic reciprocity.

  • Kronecker's proof first establishes that

::\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 () and ().

  • One of Eisenstein's proofs 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.

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.

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(\frac{98}{331}\right) &\equiv 98^{\frac{331-1}{2}} &\pmod{331} \ &\equiv 98^{165} &\pmod{331} \ &\equiv 98 \cdot (98^2)^{82} &\pmod{331} \ &\equiv 98 \cdot 5^{82} &\pmod{331} \ &\equiv 98 \cdot 25^{41} &\pmod{331} \ &\equiv 133 \cdot 25^{40} &\pmod{331} \ &\equiv 133 \cdot 294^{20} &\pmod{331} \ &\equiv 133 \cdot 45^{10} &\pmod{331} \ &\equiv 133 \cdot 39^5 &\pmod{331} \ &\equiv 222 \cdot 39^4 &\pmod{331} \ &\equiv 222 \cdot 197^2 &\pmod{331} \ &\equiv 222 \cdot 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.

Table of values

The following is a table of values of Legendre symbol \left(\frac{a}{p}\right) with p ≤ 127, a ≤ 30, p odd prime.

123456789101112131415161718192021222324252627282930357111317192329313741434753596167717379838997101103107109113127
1−101−101−101−101−101−101−101−101−101−10
1−1−1101−1−1101−1−1101−1−1101−1−1101−1−110
11−11−1−1011−11−1−1011−11−1−1011−11−1−1011
1−1111−1−1−11−101−1111−1−1−11−101−1111−1−1−1
1−111−1−1−1−111−1101−111−1−1−1−111−1101−111
11−11−1−1−111−1−1−11−111011−11−1−1−111−1−1−11
1−1−11111−11−11−1−1−1−111−101−1−11111−11−11
1111−11−111−1−111−1−11−11−1−1−1−101111−11−1
1−1−11111−11−1−1−11−1−11−1−1−11−11111−1−1101
11−111−11111−1−1−11−11−1111−1−1−1−11−1−11−1−1
1−111−1−11−11111−1−1−11−1−1−1−11−1−1−11111−11
11−111−1−1111−1−1−1−1−11−11−111−11−11−1−1−1−1−1
1−1−11−11−1−1111−111111−1−1−11−1111−1−1−1−1−1
1111−11111−1−11−11−1111−1−11−1−111−111−1−1
1−1−11−111−1111−11−1111−1−1−1−1−1−111−1−111−1
1−1111−11−11−1−11−1−1111−11111−1−111111−1
1−1111−1−1−11−1−111111−1−111−11−1−11−11−1−1−1
1−1−11−11−1−111−1−1−11111−11−1111111−1−11−1
111111−1111−11−1−111−1111−1−1−111−11−111
1111−11−111−1−11−1−1−11−111−1−1−1111−11−1−1−1
11−111−1−11111−11−1−11−1111111−111−1−1−1−1
1−111−1−11−11111−1−1−111−1−1−11−11−1111111
11−111−1−11111−1−1−1−1111−1111−1−11−1−1−1−1−1
1111−11−111−111−1−1−11−11−1−1−11−111−11−1−1−1
1−1−1111−1−11−1−1−111−111−11111111−1−1−1−11
11−11−1−1111−1−1−11111111−1−1−11−111−1111
1−111−1−1−1−1111111−11−1−11−1−1−11−11−11−111
1−1111−11−11−1−11−1−111−1−1−1111−1−111111−1
11−11−1−1111−11−11111−11−1−1−11−1−111−11−11
11−11−1−1−111−11−11−111111−111−1−111−1−1−11

Notes

References

References

  1. Legendre, A. M.. (1798). "Essai sur la théorie des nombres".
  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.
Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

modular-arithmetic quadratic-residue
Want to explore this topic further?

Ask Mako anything about Legendre symbol — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report