title: Lemma van Gauss (getaltheorie)
text: 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  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.
  
  Voorbeeld 
  Voor  en  zijn de relevante gehele 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 11 een kwadratisch residu is modulo 11 en 11 niet modulo 7, óf andersom. En inderdaad is
  
  en is 7 geen kwadratisch residu modulo 11.
  
  Voetnoten
  
  Modulair rekenen
  Gauss, lemma van