Proof of the sum of the totient over the divisors

Proof

We sort the integers $1, \dots, n$ by their greatest common divisor with $n$.

1. Let $n$ be a positive integer. For each positive divisor $d$ of $n$, let $S_d$ be the set of integers $k$ with $1 \le k \le n$ and $\gcd(k, n) = n / d$.
2. Let $1 \le k \le n$. The greatest common divisor $g = \gcd(k, n)$ is a positive divisor of $n$. So $d = n / g$ is a positive divisor of $n$, and $k \in S_d$.
3. The sets $S_d$ are pairwise disjoint, since $n / d$ determines $d$. With step 2, they partition $\{ 1, \dots, n \}$. So $n = \sum_{d \mid n} \abs{S_d}$.
4. Fix a positive divisor $d$ of $n$, and let $e = n / d$, so $n = e d$. We show that $\abs{S_d} = \varphi(d)$, where $\varphi$ is Euler's totient function.
5. If $k \in S_d$, then $e = \gcd(k, n)$ divides $k$. So $k = e j$ for an integer $j$, and $1 \le k \le n$ gives $1 \le j \le d$.
6. So it suffices to show, for $1 \le j \le d$, that $\gcd(e j, e d) = e$ if and only if $\gcd(j, d) = 1$.
7. Assume $\gcd(j, d) = c > 1$. Then $e c$ divides $e j$ and $e d$. So $\gcd(e j, e d) \ge e c > e$.
8. Assume $\gcd(j, d) = 1$. By Bézout's identity, $j u + d v = 1$ for some integers $u$ and $v$. Then $(e j) u + (e d) v = e$.
9. So each common divisor of $e j$ and $e d$ divides $e$, and is at most $e$. Since $e$ is itself a common divisor, $\gcd(e j, e d) = e$.
10. By steps 5 to 9, $k \mapsto k / e$ is a bijection from $S_d$ onto the set of $j$ with $1 \le j \le d$ and $j$ coprime to $d$. That set has $\varphi(d)$ elements, so $\abs{S_d} = \varphi(d)$.
11. By steps 3 and 10, $\sum_{d \mid n} \varphi(d) = n$.