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

[math]\displaystyle{ \sum_{d \mid n}\varphi(d) = n }[/math].

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

Neka su [math]\displaystyle{ d_1 = 1 \lt d_2 \lt ... \lt d_k = n }[/math] pozitivni djelitelji broja [math]\displaystyle{ n }[/math]. Prirodne brojeve od [math]\displaystyle{ 1 }[/math] do [math]\displaystyle{ n }[/math] razvrstajmo u [math]\displaystyle{ k }[/math] (pod)skupova: [math]\displaystyle{ D_1, D_2, ..., D_k }[/math] tako da za sve brojeve [math]\displaystyle{ x_i }[/math] u skupu [math]\displaystyle{ D_i }[/math] vrijedi [math]\displaystyle{ M(x_i, n) = d_i, }[/math] tj. u [math]\displaystyle{ i }[/math]-tu skupinu ćemo svrstati sve prirodne brojeve od [math]\displaystyle{ 1 }[/math] do [math]\displaystyle{ n }[/math] kojima je mjera s [math]\displaystyle{ n }[/math] upravo jednaka djelitelju [math]\displaystyle{ d_i. }[/math] Uočimo da ovom podjelom nijedan skup nije ostao prazan (jer skup [math]\displaystyle{ D_i }[/math] očito sadrži barem jedan element, [math]\displaystyle{ d_i, }[/math] zbog toga što je [math]\displaystyle{ M(d_i, n) = d_i }[/math]) te neki prirodni broj [math]\displaystyle{ a \in \{1, 2, ..., n\} }[/math] očito pripada nekom skupu [math]\displaystyle{ D_i }[/math] i nijednom drugom skupu [math]\displaystyle{ D_j }[/math] (za [math]\displaystyle{ i \neq j }[/math]) jer općenito vrijedi [math]\displaystyle{ M(a, b) = l_1, M(a, b) = l_2 \implies l_1 = l_2. }[/math]

Promotrimo sada neki fiksirani skup [math]\displaystyle{ D_i. }[/math] Njegovi su elementi redom [math]\displaystyle{ x_1 = d_1 \cdot 1, x_2 = d_1 \cdot y_2, ..., x_m = d_1 \cdot y_m. }[/math] Očito je maksimalna moguća vrijednost [math]\displaystyle{ y_m }[/math] jednaka [math]\displaystyle{ \frac{n}{d_i} }[/math] (jer promatramo brojeve samo u [math]\displaystyle{ \{1, 2, ..., n\} }[/math]), a ona se postiže samo ako je [math]\displaystyle{ n = 1 }[/math]). Očito je [math]\displaystyle{ M(y_i, \frac{n}{d_i}) = 1 }[/math] jer inače mjera brojeva [math]\displaystyle{ d_1y_i, n }[/math] ne bi bila [math]\displaystyle{ 1. }[/math] S druge strane, kada članove skupa [math]\displaystyle{ S_{\frac{n}{d_i}} }[/math] pomnožimo s [math]\displaystyle{ d_i }[/math] dobit ćemo brojeve kojima je mjera s n jednaka [math]\displaystyle{ d_i }[/math] jer vrijedi općenito [math]\displaystyle{ M(a, b) = 1 \iff M(ac, bc) = c }[/math] pa će ti brojevi biti elementi skupa [math]\displaystyle{ D_i }[/math] te je očito [math]\displaystyle{ |D_i| = \varphi(\frac{n}{d_i}). }[/math]

Očito je [math]\displaystyle{ \frac{n}{di} = d_j }[/math], odnosno kada [math]\displaystyle{ n }[/math] podijelimo s nekim njegovim djeliteljom rezultat je opet neki njegov djelitelj, a kako je [math]\displaystyle{ |D_1| + |D_2| + ... + |D_k| = n, }[/math] slijedi [math]\displaystyle{ \varphi(\frac{n}{d_1}) + \varphi(\frac{n}{d_2}) + ... + \varphi(\frac{n}{d_k}) = n, }[/math] što je i trebalo dokazati.

Primjer

Uzmimo [math]\displaystyle{ n = 12. }[/math] Pozitivni djelitelji broja 12 su redom {1, 2, 3, 4, 6, 12}. Raspodijelimo prirodne brojeve od 1 do 12 na gore opisani način:

[math]\displaystyle{ D_1 = \{1, 5, 7, 11\}, D_2 = \{2, 10\}, D_3 = \{3, 9\}, }[/math] [math]\displaystyle{ D_4 = \{4, 8\}, D_5 = \{6\}, D_6 = \{12\}. }[/math]

Promotrimo primjerice skup [math]\displaystyle{ D_2 = \{2 \cdot 1, 2 \cdot 5\}. }[/math] Kako je [math]\displaystyle{ 12 = 2 \cdot 6 }[/math] mora biti [math]\displaystyle{ M(1, 6) = M(5, 6) = 1, }[/math] što vrijedi. I s druge strane svi brojevi manji od 6 i relativno prosti s 6 se pojavljuju kao drugi faktor u umnošku [math]\displaystyle{ 2 \cdot 1, 2 \cdot 5. }[/math] Slično vidimo za ostale [math]\displaystyle{ D_1, D_3, D_4, D_5, D_6. }[/math]