Lemma van Gauss (getaltheorie)

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)[1]. In zijn vijfde bewijs uit 1818 bewees Gauss het lemma opnieuw[2]

LemmaBewerken

Laat   een priemgetal zijn en   een geheel getal dat relatief priem is aan  .

Beschouw van de gehele getallen   de kleinste positieve residuen modulo  . Deze residuen zijn alle verschillend; er zijn dus   residuen.

Voor het aantal   van deze residuen die groter zijn dan  , geldt:

 .

Daarin is   het Legendre-symbool.

VoorbeeldBewerken

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

 

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

 

en is 7 geen kwadratisch residu modulo 11.

VoetnotenBewerken

  1. (de) Carl Friedrich Gauss, "Neuer Beweis eines arithmetischen Satzes"; blz. 458-462 uit Untersuchungen uber Höhere Arithmetik
  2. (de) Carl Friedrich Gauss, "Neue Beweise und Erweiterungen des Fundalmentalsatzes in der Lehre von den quadratischen Reste";. blz. 496-501 uit Untersuchungen uber Höhere Arithmetik