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})$ (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}$

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

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\equiv8.$

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

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.