Gaussova lema

Gaussova lema' je teorem u elementarnoj teoriji brojeva koji daje uvjet za provjeru je li neki prirodni broj potpuni kvadrat ili nije.

Prvi se puta spominje u radovima velikog njemačkog matematičara Carla Friedricha Gaussa još 1808. godine kao treći dokaz Kvadratnog zakona reciprociteta.

Iskaz leme

Za proizvoljni neparni prosti broj $p$ neka je $a$ prirodni broj relativno prost s $p.$

Promotrimo skup $S=\{a,2a,3a,...,{\frac {p-1}{2}}a\}.$ Isto tako, promotrimo skup $S'$ najmanjih pozitivnih ostataka modulo $p$ koji daju elementi prvobitnog skupa $S.$

Neka je $n$ broj elemenata skupa $S'$ koji su veći od ${\frac {p}{2}}.$

Tada je $\left({\frac {a}{p}}\right)=(-1)^{n},$ gdje je $\left({\frac {a}{p}}\right)$ Legendreov simbol.

Dokaz

Označimo s $r_{1},r_{2},...,r_{n}$ elemente skupa $S=\{a,2a,...,{\frac {p-1}{2}}a\}$ koji su veći od ${\frac {p}{2}}$ te sa $s_{1},s_{2},...,s_{k}$ elemente skupa $S$ koji su manji od ${\frac {p}{2}}$. Očito je $n+k={\frac {p-1}{2}}.$

Kako su $r_{i}$ međusobno različiti, slijedi da su i brojevi $p-r_{i}$ međusobno različiti. Uz to, vrijedi $0<p-r_{i}<{\frac {p}{2}}$ za $i=1,2,...,n$.

Također, nijedan $p-r_{i}$ nije jednak nekom $s_{j}$. Naime, ako ako je $p-r_{i}=s_{j}$, iz $r_{i}\equiv \alpha a{\pmod {p}},s_{j}\equiv \beta a{\pmod {p}}$ bi slijedilo $a(\alpha +\beta )\equiv 0{\pmod {p}}$, što nije moguće.

Prema tome, brojevi $p-r_{1},p-r_{2},...,p-r_{n}$ te $s_{1},s_{2},...,s_{k}$ su svi međusobno različiti, ima ih ${\frac {p-1}{2}}$ i elementi su skupa $S=\{1,2,...,{\frac {p-1}{2}}.$ Zato su to upravo brojevi $1,2,...,{\frac {p-1}{2}}$ u nekom poretku.

Množeći ih, dobivamo da je $({\frac {p-1}{2}})!\equiv (p-r_{1})...(p-r_{n})s_{1}...s_{k}{\pmod {p}},$ odnosno $({\frac {p-1}{2}})!\equiv (-1)^{n}a^{\frac {p-1}{2}}({\frac {p-1}{2}})!{\pmod {p}}$ iz čega kraćenjem i korištenjem Eulerovog kriterija slijedi traženi rezultat.

Veza s MFT

Intuicija i glavne ideje

Laički rečeno, Gaussova lema na dva načina računa umnožak $a\cdot 2a\cdot ...\cdot {\frac {(p-1)}{2}}a$. Ovaj umnožak nas podsjeća na nadaleko poznati Mali Fermatov teorem (MFT). I ova lema je u mnogočemu slična s njime, samo se u njoj dakle bavimo dvama načinima gledanja na jedan te isti skup $S=\{a,2a,...,(p-1)a\}$, odnosno na umnožak prve polovice njegovih elemenata, tj. elemente $a,2a,...,{\frac {p-1}{2}}a$. Razlog tomu je što ćemo drugu polovicu (odnosno elemente ${\frac {p+1}{2}}a,...,(p-1)a$) koristiti kao negacije elemenata iz prve polovice jer vrijedi $k\equiv p-k{\pmod {p}}$ za svaki $k\in \mathbb {Z}$. (1)

Pri tome ćemo također, na prirodan način, elemente razvrstati po tome jesu li njihovi ostatci pri dijeljenju s $p$ veći ili manji od ${\frac {p}{2}}$.

Dakle, jednostavno svojstvo (1) će nam omogućiti računanje na način drugačiji od načina korištenog u MFT iz čega ćemo komputacijom i Eulerovim kriterijom dobiti traženi rezultat.

Primjer

Uzmimo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p=7,a=4} .

Dakle, imamo skup Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S=\{1,2,3,4,5,6\}} te novonastali skup Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S'=\{4,8,12,16,20,24\}} . Elementi od $S'$ redom daju ostatke Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 4,1,5,2,6,3} pri dijeljenju sa 7. Ovo nam je dobro poznato iz leme korištene u dokazu Eulerovog teorema.

Pri tome je, kako je već rečeno, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 3\equiv 7-4,1\equiv 7-6,5\equiv 7-2{\pmod {7}}.} Zato ćemo promatrati samo prvu polovicu skupa $S'$, tj. skup $\{4,8,12\}$ jer je druga samo negacija prve modulo 7. Vidimo da ostatci koji daju ovi brojevi nisu posebno omeđeni, tj. neki su veći od Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\frac {7}{2}}} , a neki su manji od tog broja.

Ako promotrimo neki ostatak Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r>{\frac {7}{2}}} (npr. Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 4} ) očito će njegova negacija, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 7-r} (dakle Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 3} ) biti manja od ${\frac {p}{2}}$ i pripadat će drugoj polovici skupa $S$.

No, evidentno taj Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 7-r} neće biti jednak nijednom elementu manjem od ${\frac {7}{2}}$ u prvoj polovici skupa $S$. (Posve analogno ako promatramo brojeve manje od ${\frac {7}{2}}$.)

Sada imamo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r_{1}=4,r_{2}=5,s_{1}=1} .

Dakle, brojeva Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 7-r_{1}=3,7-r_{2}=2,s_{1}=1} ima Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\frac {7-1}{2}}=3} , međusobno su nekongruenti modulo 7 i daju iste ostatke kao Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 4,8,12} u nekom poretku.

(U formalnom dokazu je rečeno da brojevi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p-r_{1},p-r_{2},...,p-r_{n},s_{1},s_{2},...,s_{k}} daju iste ostatke kao $a,2a,...,{\frac {p-1}{2}}a$.)

Zato su dva umnoška iz formalnog dokaza jednaka iz čega se lako dobiva tvrdnja leme.