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.
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.
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
- ↑ Andrej Dujella, Teorija brojeva, Školska knjiga, 2019.