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.
Za proizvoljni neparni prosti broj
neka je
prirodni broj relativno prost s
Promotrimo skup
Isto tako, promotrimo skup
najmanjih pozitivnih ostataka modulo
koji daju elementi prvobitnog skupa
Neka je
broj elemenata skupa
koji su veći od
Tada je
gdje je
Legendreov simbol.[1]
Označimo s
elemente skupa
koji su veći od
te sa
elemente skupa
koji su manji od
. Očito je
Kako su
međusobno različiti,[2] slijedi da su i brojevi
međusobno različiti. Uz to, vrijedi
za
.
Također, nijedan
nije jednak nekom
. Naime, ako ako je
,
iz
bi
slijedilo
, što nije moguće.
Prema tome, brojevi
te
su svi međusobno različiti, ima ih
i elementi su skupa
Zato su to upravo brojevi
u nekom poretku.
Množeći ih, dobivamo da je
odnosno
iz čega kraćenjem i korištenjem Eulerovog kriterija slijedi traženi rezultat.[3]
Laički rečeno, Gaussova lema na dva načina računa umnožak
. 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
, odnosno na umnožak prve polovice njegovih elemenata, tj. elemente
. Razlog tomu je što ćemo drugu polovicu (odnosno elemente
) koristiti kao negacije elemenata iz prve polovice jer vrijedi
za svaki
. (1)
Pri tome ćemo također, na prirodan način, elemente razvrstati po tome jesu li njihovi ostatci pri dijeljenju s
veći ili manji od
.
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.
Uzmimo
.
Dakle, imamo skup
te novonastali skup
. Elementi od
redom daju ostatke
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,
Zato ćemo promatrati samo prvu polovicu skupa
, tj. skup
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
, a neki su manji od tog broja.
Ako promotrimo neki ostatak
(npr.
) očito će njegova negacija,
(dakle
) biti manja od
i pripadat će drugoj polovici skupa
.
No, evidentno taj
neće biti jednak nijednom elementu manjem od
u prvoj polovici skupa
. (Posve analogno ako promatramo brojeve manje od
.)
Sada imamo
.
Dakle, brojeva
ima
, međusobno su nekongruenti modulo 7 i daju iste ostatke kao
u nekom poretku.
(U formalnom dokazu je rečeno da brojevi
daju iste ostatke kao
.)
Zato su dva umnoška iz formalnog dokaza jednaka iz čega se lako dobiva tvrdnja leme.
- ↑ Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
- ↑ Obrazloženje ove tvrdnje ekvivalentno je dokazu leme u članku o Eulerovom teoremu
- ↑ Gauss' Lemma