Gaussova lema

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

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^{\prime }$ najmanjih pozitivnih ostataka modulo $p$ koji daju elementi prvobitnog skupa $S.$

Neka je $n$ broj elemenata skupa $S^{\prime }$ 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(\mathrm{mod}p),s_j\equiv \beta a(\mathrm{mod}p)$ bi slijedilo $a(\alpha +\beta )\equiv 0(\mathrm{mod}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(\mathrm{mod}p),$ odnosno $(\frac{p-1}{2})!\equiv (-1{)}^n{a}^{\frac{p-1}{2}}(\frac{p-1}{2})!(\mathrm{mod}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(\mathrm{mod}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 $p=7,a=4$.

Dakle, imamo skup $S=\{1,2,3,4,5,6\}$ te novonastali skup $S^{\prime }=\{4,8,12,16,20,24\}$. Elementi od $S^{\prime }$ redom daju ostatke $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, $3\equiv 7-4,1\equiv 7-6,5\equiv 7-2(\mathrm{mod}7).$ Zato ćemo promatrati samo prvu polovicu skupa $S^{\prime }$, 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 $\frac{7}{2}$, a neki su manji od tog broja.

Ako promotrimo neki ostatak $r>\frac{7}{2}$ (npr. $4$) očito će njegova negacija, $7-r$ (dakle $3$) biti manja od $\frac{p}{2}$ i pripadat će drugoj polovici skupa $S$.

No, evidentno taj $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 $r_1=4,r_2=5,s_1=1$.

Dakle, brojeva $7-r_1=3,7-r_2=2,s_1=1$ ima $\frac{7-1}{2}=3$, međusobno su nekongruenti modulo 7 i daju iste ostatke kao $4,8,12$ u nekom poretku.

(U formalnom dokazu je rečeno da brojevi $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.