Školjka

Imamo $M(k, n) \mid n$ za sve $k\leqslant n$, pa sumu s lijeve strane možemo prikazati kao sumu po djeliteljima $n$. Potrebno je izračunati, za neki $d \mid n$, koliko postoji $k\leqslant n$ takvih da $d = M(k, n)$. Međutim, tada je očito $M(k/d, n/d) = 1$ i vrijedi $k/d \leqslant n/d$, ali i za svaki $r \leqslant n/d$ takav da $M(r, n) = 1$ je $M(rd, n) = d$, pa je dovoljno naći koliko ima takvih $r$, a to je upravo $\varphi(n/d)$. Prema tome, imamo: \[ \sum_{k = 1}^n \varphi(M(k, n)) = \sum_{d \mid n} \varphi(d) \varphi\bigg(\frac{n}{d}\bigg) \] Dovoljno je sada pokazati da $\varphi(m)\varphi(n) \leqslant \varphi(mn)$. Međutim, kako $\varphi(mn) = \varphi(m)\varphi(n)M(m, n)/\varphi(M(m, n))$ i $\varphi(n) \leqslant n$, ovo je očito. Jednakost vrijedi kad u svakoj od prethodnih nejednakosti vrijedi jednakost, to jest, kada su $d, n/d$ relativno prosti za sve vrijednosti $d \mid n$, to jest kad je $n$ kvadratno slobodan.