Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Legendre symbol

From Wikipedia, the free encyclopedia
Function in number theory
Legendre symbol (⁠a/p⁠)
for variousa (along top) andp (along left side).
a
p
012345678910
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 othera can be reduced modulop.Quadratic residues are highlighted in yellow, and correspond precisely to the values 0 and 1.

Innumber theory, theLegendre symbol is amultiplicative function with values 1, −1, 0 that is a quadratic charactermodulo of an oddprime numberp: 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 byAdrien-Marie Legendre in 1797 or 1798[1] in the course of his attempts at proving thelaw of quadratic reciprocity. Generalizations of the symbol include theJacobi symbol andDirichlet characters of higher order. The notational convenience of the Legendre symbol inspired introduction of several other "symbols" used inalgebraic number theory, such as theHilbert symbol and theArtin symbol.

Definition

[edit]

Letp{\displaystyle p} be an oddprime number. An integera{\displaystyle a} is aquadratic residue modulop{\displaystyle p} if it iscongruent to aperfect square modulop{\displaystyle p} and is a quadratic nonresidue modulop{\displaystyle p} otherwise. TheLegendre symbol is a function ofa{\displaystyle a} andp{\displaystyle p} defined as

(ap)={1if a is a quadratic residue modulo p and a≢0(modp),−1if a is a quadratic nonresidue modulo p,0if a≡0(modp).{\displaystyle \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}}}

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

(ap)≡ap−12(modp) and (ap)∈{−1,0,1}.{\displaystyle \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\}.}

ByEuler'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 convenientnotation that recorded quadratic residuosity ofa mod p. For the sake of comparison,Gauss used the notationaRp,aNp according to whethera is a residue or a non-residue modulop. For typographical convenience, the Legendre symbol is sometimes written as (a | p) or (a/p). For fixedp, the sequence(0p),(1p),(2p),…{\displaystyle \left({\tfrac {0}{p}}\right),\left({\tfrac {1}{p}}\right),\left({\tfrac {2}{p}}\right),\ldots } isperiodic with periodp and is sometimes called theLegendre sequence. Each row in the following table exhibits periodicity, just as described.

Properties of the Legendre symbol

[edit]

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

For example,
(25)=−1,F3=2,F2=1,(35)=−1,F4=3,F3=2,(55)=0,F5=5,(75)=−1,F8=21,F7=13,(115)=1,F10=55,F11=89.{\displaystyle {\begin{aligned}\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{aligned}}}

Sums of Legendre symbols

[edit]

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

Legendre symbol and quadratic reciprocity

[edit]

Letp andq be distinct odd primes. Using the Legendre symbol, thequadratic reciprocity law can be stated concisely:

(qp)(pq)=(−1)p−12⋅q−12.{\displaystyle \left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{{\tfrac {p-1}{2}}\cdot {\tfrac {q-1}{2}}}.}

Manyproofs of quadratic reciprocity are based on Euler's criterion

(ap)≡ap−12(modp).{\displaystyle \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.

∑k=0p−1ζak2=(ap)∑k=0p−1ζk2,ζ=e2πip{\displaystyle \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[4] and sixth[5] proofs of quadratic reciprocity.
(pq)=sgn⁡(∏i=1q−12∏k=1p−12(kp−iq)).{\displaystyle \left({\frac {p}{q}}\right)=\operatorname {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 ofp andq, he obtains the relation between (⁠p/q⁠) and (⁠q/p⁠).
(qp)=∏n=1p−12sin⁡(2πqnp)sin⁡(2πnp).{\displaystyle \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 certainelliptic functions instead of thesine function,Eisenstein was able to provecubic andquartic reciprocity as well.

Related functions

[edit]
  • TheJacobi symbol(an){\displaystyle \left({\frac {a}{n}}\right)} is a generalization of the Legendre symbol that allows for a composite second (bottom) argumentn, althoughn must still be odd and positive inotrud. This generalization provides an efficient way to compute all Legendre symbols without performing factorization along the way.
  • A further extension is theKronecker symbol, in which the bottom argument may be any integer.
  • Thepower residue symbol (⁠a/n⁠)n generalizes the Legendre symbol to higher powern. The Legendre symbol represents thepower residue symbol forn = 2.

Computational example

[edit]

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

(12345331)=(3331)(5331)(823331)=(3331)(5331)(161331)=(3331)(5331)(7331)(23331)=(−1)(3313)(3315)(−1)(3317)(−1)(33123)=−(13)(15)(27)(923)=−(13)(15)(27)(3223)=−(1)(1)(1)(1)=−1.{\displaystyle {\begin{aligned}\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{aligned}}}

Or using a more efficient computation:

(12345331)=(98331)=(2⋅72331)=(2331)=(−1)3312−18=−1.{\displaystyle \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 articleJacobi symbol has more examples of Legendre symbol manipulation.

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

(98331)≡98331−12(mod331)≡98165(mod331)≡98⋅(982)82(mod331)≡98⋅582(mod331)≡98⋅2541(mod331)≡133⋅2540(mod331)≡133⋅29420(mod331)≡133⋅4510(mod331)≡133⋅395(mod331)≡222⋅394(mod331)≡222⋅1972(mod331)≡222⋅82(mod331)≡−1(mod331){\displaystyle {\begin{aligned}\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{aligned}}}

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

Table of values

[edit]

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

a
p
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

Notes

[edit]
  1. ^Legendre, A. M. (1798).Essai sur la théorie des nombres. Paris. p. 186 (published on year VI of theFrench Republican calendar, thus in 1797 or 1798).
  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 inUntersuchungen ... pp. 463–495
  5. ^Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reprinted inUntersuchungen ... pp. 501–505
  6. ^Lemmermeyer, ex. p. 31, 1.34
  7. ^Lemmermeyer, pp. 236 ff.

References

[edit]

External links

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Legendre_symbol&oldid=1282776966"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp