In de getaltheorie geeft het lemma van Gauss een voorwaarde waar een geheel getal aan moet voldoen om een kwadratisch residu te zijn. Het lemma wordt bij berekeningen niet gebruikt, maar komt wel in een aantal bewijzen van kwadratische reciprociteit voor. Het lemma van Gauss verscheen voor het eerst in 1808 in Gauss' derde bewijs van kwadratische reciprociteit. , "Neuer Beweis eines arithmetischen Satzes"; blz. 458-462 uit Untersuchungen uber Höhere Arithmetik In zijn vijfde bewijs uit 1818 bewees Gauss het lemma opnieuw. , "Neue Beweise und Erweiterungen des Fundalmentalsatzes in der Lehre von den quadratischen Reste"; blz. 496-501 uit Untersuchungen uber Höhere Arithmetik
Lemma Laat een priemgetal zijn en een geheel getal dat onderling ondeelbaar is met .
Beschouw van de gehele getallen de kleinste positieve residuen modulo . Deze residuen zijn alle verschillend, dus zijn er 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.
Categorie:Modulair rekenen Gauss, lemma van