Przejdź do zawartości

Lemat Gaussa (teoria liczb)

Z Wikipedii, wolnej encyklopedii

Lemat Gaussa, kryterium Gaussa[1] – 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[2].

Twierdzenie[1][2]

[edytuj | edytuj kod]

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

[edytuj | edytuj kod]

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 można przeprowadzić elementarnymi metodami, znajdując wartość wyrażenia

.

modulo dwoma sposobami.

Z jednej strony mamy

.
(1)

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

.
(2)

Przyrównując prawe strony (1) i (2) oraz skracając przez otrzymujemy

.

Teza wynika natychmiast z kryterium Eulera, ponieważ lewa strona jest innym sposobem wyrażenia symbolu Legendre’a.

Przypisy

[edytuj | edytuj kod]
  1. a b c Adam Neugebauer, Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2020 (Matematyka olimpijska), s. 206-207, ISBN 978-83-7267-710-5 (pol.).
  2. a b c Steve Wright, Quadratic Residues and Non-Residues: Selected Topics, Lecture Notes in Mathematics, Cham: Springer, 2016, s. 16, ISBN 978-3-319-45955-4 [dostęp 2024-02-18] (ang.).