Gaussova lema o Eulerovoj funkciji

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

Lema tvrdi da je $\sum _{d\mid n}\phi (d)=n$, gdje suma prolazi skupom svih pozitivnih djelitelja od $n$.

Odnosno, zbroj vrijednosti Eulerove funkcije u svim pozitivnim djeliteljima nekog prirodnog broja upravo je jednak tom broju.

Gauss je svoj dokaz izveo rabeći se metodama teorije grupa.Predložak:Ni Dokaz ispod blizak je njegovom, iako je elementarniji 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\ne j$) jer općenito vrijedi $M(a,b)=l_1,M(a,b)=l_2⟹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⟺M(ac,bc)=c$ pa će ti brojevi biti elementi skupa $D_i$ te je očito $|D_i|=\phi (\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 $\phi (\frac{n}{d_1})+\phi (\frac{n}{d_2})+...+\phi (\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.$