# 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{\displaystylep}-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.
* ↑ AM Legendre. Essai sur la theorie des nombres, 1798. blz 186
* ↑ In een postuum artikel door Euler (1783), en door Legendre in 1786 opgesteld. Als eerste bewezen door Gauss in 1796, gepubliceerd in DA (1801); arts. 107-144 (eerste bewijs), arts 253-262 (tweede bewijs)
* ↑ Lemmermeyer, blz 14 "zelfs in een zo simpel geval even als de bikwadratische reciprociteit moet we tussen vier verschillende symbolen onderscheiden, namelijk de kwadratische en bikwadratische residu symbolen in Z[i], het Legendre-symbool in Z, en het rationele vierdegraads residu-symbool in Z ... "
* ↑ Van Z/pZ$^×$ naar C$_2$, wat de ondergroep {-1,1} is van C. De logaritme en de exponent zijn oudere homomorfismen.
* ↑ Jeong-Heon Kim en Hong-Yeop Song, "Trace Representation of Legendre Sequences," Designs, Codes, and Cryptography 24, p. 343–348 (2001).
* ↑ Engelstalige Wikipedia. Euler's criterion.
* ↑ YouTube. Euler's Criterion: Proof and Example.