Toggle menu
310,1 tis.
50
18
525,6 tis.
Hrvatska internetska enciklopedija
Toggle preferences menu
Toggle personal menu
Niste prijavljeni
Your IP address will be publicly visible if you make any edits.

Gaussova lema

Izvor: Hrvatska internetska enciklopedija

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.[1]

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

  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