Legendre-symbool

Het Legendre-symbool of kwadratisch karakter is een functie, die in 1798 door Adrien-Marie Legendre werd ingevoerd. Hij deed dat toen hij stellingen probeerde te bewijzen ten aanzien van de kwadratische reciprociteit. Het Legendre-symbool heeft als voorbeeld gediend voor andere hogere machts residu-symbolen, zoals voor het Jacobi- en het Kronecker-symbool. Het is een van de eerste voorbeelden van een homomorfisme.

Definitie

Het Legendre-symbool $\left({\tfrac {a}{p}}\right)$, soms geschreven als $\left(a|p\right)$, wordt voor hele getallen $a$ en priemgetallen $p$ gedefinieerd door:

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

Als $a|p=1$ wordt $a$ een kwadratisch residu genoemd ${\text{mod}}\ p$, als $a|p=-1$, dan wordt $a$ een kwadratisch niet-residu ${\text{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 $\left(a|p\right)$ voor $a$ 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}.

Eigenschappen

Het Legendre-symbool is periodiek met periode $p$, dus hangt alleen van de restklasse van $a\ {\text{mod}}\ p$ af.

De kwadratische residuen ${\text{mod}}\ p$ vormen een ondergroep met index 2 in de vermenigvuldigingsgroep $\mathbb {Z} /p\mathbb {Z} ^{*}$. Dus van de restklassen ${\text{mod}}\ 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}}\mod {p}$

Of: als $p$ een oneven priemgetal is, en $a$ geen veelvoud van $p$, dan is $a$ een kwadratisch residu ${\text{mod}}\ p$ als en slechts als $a$^($p$-1)/2-1 een veelvoud is van $p$, en een kwadratisch niet-residu ${\text{mod}}\ 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$

maar we kunnen 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$

Andere symbolen

• 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