Lemma van Gauss (getaltheorie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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]

Lemma[bewerken]

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, \dots, \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[bewerken]

Voor p=11 en a=7 zijn de relevante gehel 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.

Voetnoten[bewerken]

  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