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].
Niech
będzie liczbą pierwszą oraz
będzie niepodzielne przez
. Rozważmy zbiór
![{\displaystyle S=\{a,2a,3a,\dots ,\textstyle {\frac {p-1}{2}}a\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7a922303140cce4553d995cdc77f5c46ccb344c)
Niech
będzie liczbą tych elementów zbioru
, które dają przy dzieleniu przez
resztę większą od
. Wówczas
![{\displaystyle \left({\frac {a}{p}}\right)=(-1)^{v},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80c9d71b0a575a741d5d92c9e896aa46dac022ea)
gdzie
jest symbolem Legendre’a.
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
| | ![{\displaystyle {\mid }x{\mid }={\begin{cases}{\phantom {-}}x&{\mbox{gdy }}1\leq (x{\mod p})\leq {\frac {p-1}{2}},\\-x&{\mbox{gdy }}{\frac {p+1}{2}}\leq (x{\mod p})\leq p-1.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b15c2cd98ecf0c047915fdab5e102791170964b3) |
|
|
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.
- ↑ a b c AdamA. Neugebauer AdamA., Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2020 (Matematyka olimpijska), s. 206-207, ISBN 978-83-7267-710-5 (pol.).
- ↑ a b c SteveS. Wright SteveS., 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.).