Gaussova lema o Eulerovoj funkciji

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 lemeUredi

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.

PrimjerUredi

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  

IzvoriUredi

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