Legendre-symbool

Het Legendre-symbool of kwadratisch karakter is een functie, die in 1798 werd geïntroduceerd door Adrien-Marie Legendre tijdens zijn gedeeltelijk succesvolle poging om de wet van de kwadratische reciprociteit te bewijzen.Het Legendre-symbool heeft als prototype gediend voor diverse 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.

Definitie

Het Legendre-symbool $({\tfrac {a}{p}})$$({\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}}$$\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 {R} p$, $a\mathrm {N} 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}.

Elementaire eigenschappen

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} ^{*}$$\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

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

$\left({\tfrac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}$$\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

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\equiv 8.$$12^{2}=144\equiv 8.$

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.$$8^{\frac {17-1}{2}}=8^{8}=64^{4}\equiv 13^{4}=169^{2}\equiv (-1)^{2}=1.$

Gerelateerde functies

• 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.