Lemat Gaussa (teoria liczb)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Lemat Gaussa – lemat zadający warunki, które musi spełniać liczba całkowita, aby była resztą kwadratową. Pierwszy raz użył go Carl Friedrich Gauss w dowodzie prawa wzajemności reszt kwadratowych.

Treść lematu[edytuj]

Dla dowolnej nieparzystej liczby pierwszej niech będzie względnie pierwsze z .

Rozważmy liczby:

i ich reszty modulo . (wszystkie reszty są różne, więc jest ich )

Niech będzie liczbą tych reszt które są większe niż . Wtedy

gdzie jest symbolem Legendre'a.

Dowód[edytuj]

Dowód[1] można przeprowadzić elementarnymi metodami porównując wartość wyrażenia

modulo p liczoną dwoma sposobami. Z jednej strony mamy

Do policzenia wartości innym sposobem na potrzeby dowodu definiujemy wartość jako

Skoro zlicza wielokrotności dla których reszty modulo należą do drugiego warunku definicji, zaś wtedy reszty modulo z wielokrotności są pod pierwszym warunkiem, mamy

Zauważmy teraz że wartości reszt modulo p są parami różne dla .

Istotnie, jeśli , dla , wtedy , czyli , więc

, bo większe od i mniejsze od , ale reszt jest

dokładnie , więc muszą one być permutacją zbioru . Zatem

Porównując to z pierwszym rezultatem i skracając przez otrzymując

.

Co kończy dowód na podstawie kryterium Eulera, gdyż lewa strona jest alternatywnym sposobem na wyrażenia symbolu Legendre'a.

Przykład[edytuj]

Dobierając and , ciąg liczb to:

.

Po przeprowadzeniu dzielenia modulo otrzymujemy reszty:

.

Trzy z nich są większe od , więc . Z lematu otrzymujemy, że

.

Co istotnie jest prawdą, ponieważ 7 nie jest resztą kwadratową modulo 11.

Przypisy

  1. Any textbook on elementary number theory will have a proof. The one here is basically Gauss's from "Neuer Beweis eines arithnetischen Satzes"; pp 458-462 of Untersuchungen uber hohere Arithmetik