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

$\sum _{d\mid n}\varphi (d)=n$.

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 $d_{1}=1<d_{2}<...<d_{k}=n$ pozitivni djelitelji broja $n$. Prirodne brojeve od $1$ do $n$ razvrstajmo u $k$ (pod)skupova: $D_{1},D_{2},...,D_{k}$ tako da za sve brojeve $x_{i}$ u skupu $D_{i}$ vrijedi $M(x_{i},n)=d_{i},$ tj. u $i$-tu skupinu ćemo svrstati sve prirodne brojeve od $1$ do $n$ kojima je mjera s $n$ upravo jednaka djelitelju $d_{i}.$ Uočimo da ovom podjelom nijedan skup nije ostao prazan (jer skup $D_{i}$ očito sadrži barem jedan element, $d_{i},$ zbog toga što je $M(d_{i},n)=d_{i}$) te neki prirodni broj $a\in \{1,2,...,n\}$ očito pripada nekom skupu $D_{i}$ i nijednom drugom skupu $D_{j}$ (za $i\neq j$) jer općenito vrijedi $M(a,b)=l_{1},M(a,b)=l_{2}\implies l_{1}=l_{2}.$

Promotrimo sada neki fiksirani skup $D_{i}.$ Njegovi su elementi redom $x_{1}=d_{1}\cdot 1,x_{2}=d_{1}\cdot y_{2},...,x_{m}=d_{1}\cdot y_{m}.$ Očito je maksimalna moguća vrijednost $y_{m}$ jednaka ${\frac {n}{d_{i}}}$ (jer promatramo brojeve samo u $\{1,2,...,n\}$), a ona se postiže samo ako je $n=1$). Očito je $M(y_{i},{\frac {n}{d_{i}}})=1$ jer inače mjera brojeva $d_{1}y_{i},n$ ne bi bila $1.$ S druge strane, kada članove skupa $S_{\frac {n}{d_{i}}}$ pomnožimo s $d_{i}$ dobit ćemo brojeve kojima je mjera s n jednaka $d_{i}$ jer vrijedi općenito $M(a,b)=1\iff M(ac,bc)=c$ pa će ti brojevi biti elementi skupa $D_{i}$ te je očito $|D_{i}|=\varphi ({\frac {n}{d_{i}}}).$

Očito je ${\frac {n}{di}}=d_{j}$, odnosno kada $n$ podijelimo s nekim njegovim djeliteljom rezultat je opet neki njegov djelitelj, a kako je $|D_{1}|+|D_{2}|+...+|D_{k}|=n,$ slijedi $\varphi ({\frac {n}{d_{1}}})+\varphi ({\frac {n}{d_{2}}})+...+\varphi ({\frac {n}{d_{k}}})=n,$ što je i trebalo dokazati.

Primjer

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

$D_{1}=\{1,5,7,11\},D_{2}=\{2,10\},D_{3}=\{3,9\},$ $D_{4}=\{4,8\},D_{5}=\{6\},D_{6}=\{12\}.$

Promotrimo primjerice skup $D_{2}=\{2\cdot 1,2\cdot 5\}.$ Kako je $12=2\cdot 6$ mora biti $M(1,6)=M(5,6)=1,$ što vrijedi. I s druge strane svi brojevi manji od 6 i relativno prosti s 6 se pojavljuju kao drugi faktor u umnošku $2\cdot 1,2\cdot 5.$ Slično vidimo za ostale $D_{1},D_{3},D_{4},D_{5},D_{6}.$