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 ,\textstyle {\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 $\textstyle {\frac {p-1}{2}}$. Wówczas

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

gdzie $\textstyle \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 $\textstyle {\frac {11}{2}}$, czyli $v=3$. Na mocy lematu Gaussa, otrzymujemy

$\left({\frac {7}{11}}\right)=(-1)^{3}=-1$,

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

$Z=a\cdot 2a\cdot 3a\cdot \ldots \cdot \textstyle {\frac {p-1}{2}}a$.

modulo $p$ dwoma sposobami.

Z jednej strony mamy

$Z=a^{(p-1)/2}\left(1\cdot 2\cdot 3\cdot \ldots \cdot \textstyle {\frac {p-1}{2}}\right)$.

(1)

Z drugiej strony możemy zdefiniować wartość $|x|$ jako

${\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}}$

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

$Z=(-1)^{v}\left(|a|\cdot |2a|\cdot |3a|\cdot \ldots \cdot \left|\textstyle {\frac {p-1}{2}}a\right|\right)$.

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

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

$Z\equiv (-1)^{v}\left(1\cdot 2\cdot 3\cdot \ldots \cdot {\frac {p-1}{2}}\right){\pmod {p}}$.

(2)

Przyrównując prawe strony (1) i (2) oraz skracając przez $1\cdot 2\cdot 3\cdot \ldots \cdot \textstyle {\frac {p-1}{2}}\not \equiv 0,$ otrzymujemy

$a^{\frac {p-1}{2}}\equiv (-1)^{v}$.

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