The sum of φ(d) over the divisors of n

Idea. Count the same set of $n$ objects in two ways: all together, and grouped according to the denominator in lowest terms.

Grouping. Take $k\in\{1,\dots,n\}$ and write $\frac kn=\frac ad$ in lowest terms, i.e. $\gcd(a,d)=1$ and $1\le a\le d$. The denominator $d$ divides $n$ (because $\frac kn=\frac ad$ gives $kd=an$, and $\gcd(a,d)=1$ forces $d\mid n$).

Counting a group. Fix a divisor $d$ of $n$. A fraction $\frac kn$ has lowest-terms denominator $d$ exactly when it equals $\frac ad$ with $1\le a\le d$ and $\gcd(a,d)=1$. Each such $a$ gives exactly one $k=a\cdot\frac nd$, and distinct $a$ give distinct fractions. Hence exactly $\varphi(d)$ of the fractions $\frac kn$ have denominator $d$.

Conclusion. Every one of the $n$ fractions has exactly one lowest-terms denominator $d\mid n$, so
$$n=\sum_{d\mid n}\varphi(d).$$

Check. $n=12$: $\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=1+1+2+2+2+4=12$.

Lesson. Classify the elements of a set by an invariant (here the reduced denominator) and count each class.