Gaussova lema o Eulerovoj funkciji

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

Gaussova lema o Eulerovoj funkciji je rezultat u elementarnoj teoriji brojeva kojega je dokazao veliki njemački matematičar Carl Friedrich Gauss u 19. stoljeću, koji omogućuje lakše računanje Eulerove funkcije.

Lema tvrdi

.[1]

Gauss je svoj dokaz izveo elegantno koristeći teoriju grupa, a dokaz ispod blizak je njegovom, no ipak je nešto elementarniji, ali i podrobniji.

Dokaz leme[uredi | uredi kôd]

Neka su pozitivni djelitelji broja . Prirodne brojeve od do razvrstajmo u (pod)skupova: tako da za sve brojeve u skupu vrijedi tj. u -tu skupinu ćemo svrstati sve prirodne brojeve od do kojima je mjera s upravo jednaka djelitelju Uočimo da ovom podjelom nijedan skup nije ostao prazan (jer skup očito sadrži barem jedan element, zbog toga što je ) te neki prirodni broj očito pripada nekom skupu i nijednom drugom skupu (za ) jer općenito vrijedi .

Promotrimo sada neki fiksirani skup Njegovi su elementi redom Očito je maksimalna moguća vrijednost jednaka (jer promatramo brojeve samo u ), a ona se postiže samo ako je ). Očito je jer inače mjera brojeva ne bi bila S druge strane, kada članove skupa pomnožimo s dobit ćemo brojeve kojima je mjera s n jednaka jer vrijedi općenito pa će ti brojevi biti elementi skupa te je očito

Očito je , odnosno kada podijelimo s nekim njegovim djeliteljom rezultat je opet neki njegov djelitelj, a kako je slijedi što je i trebalo dokazati.

Primjer[uredi | uredi kôd]

Uzmimo Pozitivni djelitelji broja 12 su redom {1, 2, 3, 4, 6, 12}. Raspodijelimo prirodne brojeve od 1 do 12 na gore opisani način:

Promotrimo primjerice skup Kako je mora biti što vrijedi. I s druge strane svi brojevi manji od 6 i relativno prosti s 6 se pojavljuju kao drugi faktor u umnošku Slično vidimo za ostale

Izvori[uredi | uredi kôd]

  1. Andrej Dujella, Teorija brojeva, Školska knjiga, 2019.