Lemat Gaussa (teoria liczb)

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

Twierdzenie

Niech $p>2$ będzie liczbą pierwszą oraz $a$ będzie niepodzielne przez $p$. Rozważmy zbiór

$S=\{a,2a,3a,\dots ,\frac{p-1}{2}a\}.$

Niech $v$ będzie liczbą tych elementów zbioru $S$, które dają przy dzieleniu przez $p$ resztę większą od $\frac{p-1}{2}$. Wówczas

$\left(\frac{a}{p}\right)=(-1{)}^v,$

gdzie $\left(\frac{a}{p}\right)$ jest symbolem Legendre’a.

Przykład

Rozważmy $p=11$ oraz $a=7$. Wówczas $S=\{7,14,21,28,35\}.$ Elementy zbioru $S$ dają kolejno reszty 7, 3, 10, 6 i 2 z dzielenia przez $11$. Dokładnie trzy z nich są większe od $\frac{11}{2}$, czyli $v=3$. Na mocy lematu Gaussa, otrzymujemy Szablon:Wzór 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 Szablon:Wzór modulo $p$ dwoma sposobami.

Z jednej strony mamy Szablon:Wzór

Z drugiej strony możemy zdefiniować wartość $|x|$ jako Szablon:Wzór

Skoro $v$ jest liczbą wielokrotności $ka$ dla $k=1,2,3,\dots ,\frac{p-1}{2}$, których reszty modulo $p$ spełniają drugi warunek powyższej definicji, mamy Szablon:Wzór

Zauważmy teraz, że wartości $|ka|$ modulo $p$ są parami różne dla $k=1,2,3,\dots ,\frac{p-1}{2}.$ Istotnie $|xa|\equiv |ya|(\mathrm{mod}p)$ implikuje $xa\equiv ya(\mathrm{mod}p)$ lub $xa\equiv -ya(\mathrm{mod}p)$. Jeśli $xa\equiv ya(\mathrm{mod}p)$, to $x\equiv y(\mathrm{mod}p)$, co daje $x=y$. Niemożliwe jest również $xa\equiv -ya(\mathrm{mod}p)$, bo wynika stąd $x+y\equiv 0(\mathrm{mod}p)$, a to nie zachodzi dla $1⩽x,y⩽\frac{p-1}{2}$.

Ponadto, ponieważ $|x|$ przyjmuje jedynie wartości $1,2,\dots ,\frac{p-1}{2}$ modulo $p$, a rozważanych wartości $|ka|$ jest dokładnie $\frac{p-1}{2}$, ich reszty modulo $p$ stanowią permutację wartości $1,2,3,\dots ,\frac{p-1}{2}$. Zatem Szablon:Wzór

Przyrównując prawe strony Szablon:LinkWzór i Szablon:LinkWzór oraz skracając przez $1\cdot 2\cdot 3\cdot \dots \cdot \frac{p-1}{2}\equiv ̸0,$ otrzymujemy Szablon:Wzór Teza wynika natychmiast z kryterium Eulera, ponieważ lewa strona jest innym sposobem wyrażenia symbolu Legendre’a.