Prijeđi na sadržaj

Gaussova lema

Izvor: Wikipedija

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

[uredi | uredi kôd]

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

[uredi | uredi kôd]

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

[uredi | uredi kôd]

Intuicija i glavne ideje

[uredi | uredi kôd]

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

[uredi | uredi kôd]

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

[uredi | uredi kôd]
  1. Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
  2. Obrazloženje ove tvrdnje ekvivalentno je dokazu leme u članku o Eulerovom teoremu
  3. Gauss' Lemma