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 lemeUredi

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]

DokazUredi

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]

Veza s MFTUredi

Intuicija i glavne idejeUredi

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.

PrimjerUredi

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.

IzvoriUredi

  1. Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
  2. Obrazloženje ove tvrdnje ekvivalentno je dokazu leme u članku o Eulerovom teoremu
  3. https://crypto.stanford.edu/pbc/notes/numbertheory/gausslemma.html