Lemma van Gauss (getaltheorie)

In de getaltheorie geeft het lemma van Gauss een voorwaarde voor een geheel getal om een kwadratisch residu te zijn. Hoewel het lemma geen rol speelt in berekeningen, heeft het lemma theoretisch belang, aangezien het voorkomt in een aantal bewijzen van kwadratische reciprociteit

Het lemma van Gauss verscheen voor het eerst in Carl Friedrich Gauss' derde bewijs van kwadratische reciprociteit (1808). In zijn vijfde bewijs uit 1818 bewees Gauss het lemma opnieuw

Lemma

Laat $p>2$ een priemgetal zijn en $a$ een geheel getal dat relatief priem is aan $p$.

Beschouw van de gehele getallen $a,2a,3a,\ldots ,{\tfrac {p-1}{2}}a$ de kleinste positieve residuen modulo $p$. Deze residuen zijn alle verschillend; er zijn dus $(p-1)/2$ residuen.

Voor het aantal $n$ van deze residuen die groter zijn dan $p/2$, geldt:

$\left({\frac {a}{p}}\right)=(-1)^{n}$

Daarin is $\left({\tfrac {a}{p}}\right)$ het legendre-symbool.

Voorbeeld

Voor $p=11$ en $a=7$ zijn de relevante gehele getallen: 7, 14, 21, 28, 35. Reductie modulo 11 geeft de rij: 7, 3, 10, 6, 2. Daarvan zijn er $n=3$ groter dan 11/2. Volgens het lemma van Gauss is dus:

$\left({\frac {7}{11}}\right)=(-1)^{3}=-1$,

wat inhoudt dat óf 11 een kwadratisch residu is modulo 11 en 11 niet modulo 7, óf andersom. En inderdaad is

$5^{2}\equiv 11{\pmod {7}}$

en is 7 geen kwadratisch residu modulo 11.