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

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

${\displaystyle \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 ${\displaystyle a|p=1}$ wordt ${\displaystyle a}$ een kwadratisch residu genoemd ${\displaystyle {\text{mod}}\ p}$, als ${\displaystyle a|p=-1}$, dan wordt ${\displaystyle a}$ een kwadratisch niet-residu ${\displaystyle {\text{mod}}\ p}$ genoemd. Het is gebruikelijk om nul als een speciaal geval te behandelen.

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

De periodieke rij ${\displaystyle \left(a|p\right)}$ voor ${\displaystyle 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}.^[5]

Eigenschappen

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

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

Criterium van Euler

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

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

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

${\displaystyle 12^{2}=144\equiv 8}$

maar we kunnen ook het criterium van Euler gebruiken en nagaan dat

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