Lemat Gaussa (teoria liczb)

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

Twierdzenie^[1]^[2]

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^[1]^[2]

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.

Przypisy

↑ ^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.).

[:0-1] 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.).

[:1-2] 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.).

[1]

[2]

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Lemat Gaussa (teoria liczb)

Twierdzenie^[1]^[2]

Przykład

Dowód^[1]^[2]

Przypisy

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Twierdzenie[1][2]

Przykład

Dowód[1][2]

Przypisy

Twierdzenie^[1]^[2]

Dowód^[1]^[2]