Lemat Gaussa, kryterium Gaussa – lemat zadający warunki, które musi spełniać liczba całkowita, aby była resztą kwadratową modulo , gdzie jest liczbą pierwszą. Pierwszy raz użył go Carl Friedrich Gauss w dowodzie prawa wzajemności reszt kwadratowych.
Twierdzenie Niech będzie liczbą pierwszą oraz będzie niepodzielne przez . Rozważmy zbiór
Niech będzie liczbą tych elementów zbioru , które dają przy dzieleniu przez resztę większą od . Wówczas
gdzie jest symbolem Legendre’a.
Przykład Rozważmy oraz . Wówczas Elementy zbioru dają kolejno reszty 7, 3, 10, 6 i 2 z dzielenia przez . Dokładnie trzy z nich są większe od , czyli . Na mocy lematu Gaussa, otrzymujemy
co jest prawdą, ponieważ 7 nie jest resztą kwadratową modulo 11. Są nimi tylko 0, 1, 3, 4, 5 oraz 9.
Dowód Dowód można przeprowadzić elementarnymi metodami, znajdując wartość wyrażenia
modulo dwoma sposobami.
Z jednej strony mamy
Z drugiej strony możemy zdefiniować wartość jako
Skoro jest liczbą wielokrotności dla , których reszty modulo spełniają drugi warunek powyższej definicji, mamy
Zauważmy teraz, że wartości modulo są parami różne dla Istotnie implikuje lub . Jeśli , to , co daje . Niemożliwe jest również , bo wynika stąd , a to nie zachodzi dla .
Ponadto, ponieważ przyjmuje jedynie wartości modulo , a rozważanych wartości jest dokładnie , ich reszty modulo stanowią permutację wartości . Zatem
Przyrównując prawe strony i oraz skracając przez otrzymujemy
Teza wynika natychmiast z kryterium Eulera, ponieważ lewa strona jest innym sposobem wyrażenia symbolu Legendre’a.
Przypisy
Linki zewnętrzne [dostęp 2025-12-04].
G Kategoria:Twierdzenia arytmetyki modularnej