Legendre-symbool

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het Legendre-symbool of kwadratisch karakter is een functie, die in 1798 werd geïntroduceerd [1]door Adrien-Marie Legendre tijdens zijn gedeeltelijk succesvolle poging om de wet van de kwadratische reciprociteit te bewijzen.[2]Het Legendre-symbool heeft als prototype gediend voor diverse[3] hogere machts residu-symbolen; andere uitbreidingen en veralgemeningen zijn het Jacobi-symbool, het Kronecker-symbool, het Hilbert-symbool en het Artin-symbool. Het is een van de eerste voorbeelden van een homomorfisme.[4]

Definitie[bewerken]

Het Legendre-symbool (\tfrac{a}{p}) (conform typografische conventies soms geschreven als (a|p) ) wordt voor geheel getallen a en positieve oneven priemgetallen p gedefinieerd door:


\left(\frac{a}{p}\right) = \begin{cases}
\;\;\,0\mbox{ als } a \equiv 0 \pmod{p}
\\+1\mbox{ als }a \not\equiv 0\pmod{p} \mbox{ en voor zeker geheel getal }x, \;x^2\equiv \;a \pmod{p}
\\-1\mbox{ als een dergelijke } x \mbox{ niet bestaat.}\end{cases}

Als (a|p) = 1, dan wordt a een kwadratisch residu genoemd (mod p); als (a|p) = −1, dan wordt a een kwadratisch niet-residu (mod p) genoemd.
Het is gebruikelijk om nul als een speciaal geval te behandelen.

Gauss gebruikte de notatie a\mathrm{R}p, a\mathrm{N}p afhankelijk van het feit of a een residu of een niet-residu van p is.

De periodieke rij (a|p) voor a gelijk aan 0,1,2,... wordt soms de Legendre-rij genoemd, met de {0,1,-1} waarden soms weergegeven door respectievelijk {1,0,1} of {0,1,0}.[5]

Elementaire eigenschappen[bewerken]

Het Legendre-symbool is periodiek met periode p, en hangt dus slechts af van de restklasse van a modulo p.

De kwadratische residuen modulo p vormen een ondergroep met index 2 in de vermenigvuldigingsgroep \mathbb{Z}/p\mathbb{Z}^*. Dus van de restklassen modulo p die niet de nulklasse zijn, is precies de helft een kwadraat.

Criterium van Euler[bewerken]

Het criterium van Euler[6] laat een rechtstreekse berekening van het Legendre-symbool toe:

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

Uitgedrukt in woorden: als p een oneven priemgetal is, en a geen veelvoud van p, dan is a een kwadratisch residu modulo p als en slechts als a(p-1)/2-1 een veelvoud is van p, en een kwadratisch niet-residu modulo p als en slechts als a(p-1)/2+1 een veelvoud is van p.

Voorbeeld[bewerken]

Om na te gaan of 8 congruent is met een kwadraat modulo 17, kunnen we alle kwadraten modulo 17 uitrekenen, om vast te stellen dat

12^2=144\equiv8.

We kunnen echter ook het criterium van Euler gebruiken en nagaan dat

8^\frac{17-1}2=8^8=64^4\equiv 13^4=169^2\equiv(-1)^2=1.

Gerelateerde functies[bewerken]

  • Het Jacobi-symbool is een veralgemening van het Legendre-symbool. dat samengestelde laagste getallen toestaat, hoewel het laagste getal nog steeds oneven en positief moet zijn. Deze veralgemening geeft een doeltreffende methode om alle Legendre-symbolen te berekenen.
  • Een verdere veralgemening is het Kronecker-symbool dat de laagste getallen uitbreidt naar alle gehele getallen.

Voetnoten[bewerken]

  1. A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186
  2. In een postuum artikel door Euler (1783), en door Legendre in 1786 opgesteld. Als eerste bewezen door Gauss in 1796, gepubliceerd in DA (1801); arts. 107-144 (eerste bewijs), arts 253-262 (tweede bewijs)
  3. Lemmermeyer, p.xiv "zelfs in een zo simpel geval even als de bikwadratische reciprociteit moet we tussen vier verschillende symbolen onderscheiden, namelijk de kwadratische en bikwadratische residu symbolen in Z[i], het Legendre-symbool in Z, en het rationele vierdegraads residu-symbool in Z ... "
  4. Van Z/pZ× naar C2, wat de ondergroep {-1,1} is van C. ("log" en "exp" zijn oudere homomorfismen)
  5. Jeong-Heon Kim en Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).
  6. Pierre Samuel, "Théorie algébrique des nombres," 2e uitgave Hermann, Parijs 1971, blz. 92