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(\frac{a}{p}\right)$, soms geschreven als $(a|p)$, wordt voor hele getallen $a$ en priemgetallen $p$ gedefinieerd door:

$\left(\frac{a}{p}\right)=\{\begin{array}{c}0\text{ als }a\equiv 0modp\\ +1\text{ als }a\equiv ̸0modp\text{ en voor zeker heel getal }x,x^2\equiv amodp\\ -1\text{ als een dergelijke }x\text{ niet bestaat }\end{array}$

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

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.