Legendre-symbool
Het Legendre-symbool of kwadratisch karakter is een functie, die in 1798 door Adrien-Marie Legendre werd ingevoerd.[1] Hij deed dat toen hij stellingen probeerde te bewijzen ten aanzien van de kwadratische reciprociteit.[2] Het Legendre-symbool heeft als voorbeeld gediend voor andere[3] hogere machts residu-symbolen, zoals voor het Jacobi- en het Kronecker-symbool. Het is een van de eerste voorbeelden van een homomorfisme.[4]
Definitie
[bewerken | brontekst bewerken]Het Legendre-symbool , soms geschreven als , wordt voor hele getallen en priemgetallen gedefinieerd door:
Als wordt een kwadratisch residu genoemd , als , dan wordt een kwadratisch niet-residu genoemd. Het is gebruikelijk om nul als een speciaal geval te behandelen.
Gauss gebruikte de notatie , afhankelijk van het feit of een residu of een niet-residu van is.
De periodieke rij voor gelijk aan 0, 1, 2,... wordt soms de Legendre-rij genoemd, met de {0,1,-1} waarden soms weergegeven door {1,0,1} of {0,1,0}.[5]
Eigenschappen
[bewerken | brontekst bewerken]Het Legendre-symbool is periodiek met periode , dus hangt alleen van de restklasse van af.
De kwadratische residuen vormen een ondergroep met index 2 in de vermenigvuldigingsgroep . Dus van de restklassen die niet de nulklasse zijn, is precies de helft een kwadraat.
Criterium van Euler
[bewerken | brontekst bewerken]Het criterium van Euler[6][7] laat een rechtstreekse berekening van het Legendre-symbool toe:
Of: als een oneven priemgetal is, en geen veelvoud van , dan is een kwadratisch residu als en slechts als (-1)/2-1 een veelvoud is van , en een kwadratisch niet-residu als en slechts als een veelvoud is van .
Voorbeeld
[bewerken | brontekst 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
maar we kunnen ook het criterium van Euler gebruiken en nagaan dat
Andere symbolen
[bewerken | brontekst 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.
- ↑ AM Legendre. Essai sur la theorie des nombres, 1798. blz 186
- ↑ 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)
- ↑ Lemmermeyer, blz 14 "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 ... "
- ↑ Van Z/pZ× naar C2, wat de ondergroep {-1,1} is van C.
De logaritme en de exponent zijn oudere homomorfismen. - ↑ Jeong-Heon Kim en Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).
- ↑ Engelstalige Wikipedia. Euler's criterion.
- ↑ YouTube. Euler's Criterion: Proof and Example.