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  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.

Dokaz 
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, 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.

Veza s MFT

Intuicija i glavne ideje 
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.

Primjer
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.

Izvori

Matematika