Školjka

Neka je $M(a, b)$ najveći zajednički djelitelj prirodnih brojeva $a, b$. Neka je $\varphi(n)$ broj prirodnih brojeva $k \leqslant n$ takvih da $M(k, n) = 1$, a neka je $\tau(n)$ broj djeljitelja $n$. Dokaži: \[\sum_{k = 1}^n \varphi(M(k, n)) \leqslant \varphi(n)\tau(n)\] Kada vrijedi jednakost? \begin{flushright}\emph{(Borna Šimić)}\end{flushright}