Theorem
$$
\begin{align*}
\sum_{d\mid n} \phi(d) = n
\end{align*}
$$
Proof
Let \(S_n = \{1,2,3,\ldots, n\}\) and let \(A_d = \{ x \leq n, \gcd(x,n) = d\}\). That is, \(A_d\) is the set of integers less than or equal to \(n\) such that their greatest common divisor with \(n\) is \(d\).
Take \(n = 12\). Then \(A_6 = \{6\}\), \(A_3 = \{3,9\}\), \(A_4 = \{4,8\}\), \(A_{12} = \{12\}\), \(A_1 = \{1,5,7,11\}\), \(A_2 = \{2, 10\}\)
Observe that for any \(i \neq j\), \(A_i \cap A_j = \emptyset\) since if \(\gcd(a,n) = i\) for some element \(a \leq n\), then clearly \(\gcd(a,j) \neq \gcd(a,j)\). Furthermore, for any integer \(m \in S_n\), we must have \(m \in A_d(n)\) where \(d = \gcd(n,m)\). So any \(m \in S_n\), is in one of the subsets \(A_d\). Therefore,
$$
\begin{align*}
n = |S_n| = \sum_{d\mid n} |A_d(n)|
\end{align*}
$$
Next, we claim that \(|A_d(n)| = \phi(n/d)\). To see this, observe that
$$
\begin{align*}
|A_d| &= |\{ x \leq n, \gcd(x,n) = d\}| \\
&= |\{ x \leq n, \gcd(x/d,n/d) = 1\}| \\
&= \phi(n/d)
\end{align*}
$$
But then, it is easy to see that
$$
\begin{align*}
\sum_{d\mid n} \phi(d) &= \sum_{d\mid n} \phi(n/d)
\end{align*}
$$
(One can simply construct a bijection that sends \(d\) to \(n/d\)). Thus
$$
\begin{align*}
n = \sum_{d\mid n} \phi(d). \quad \blacksquare
\end{align*}
$$
References
- Wikipedia
- Number Theory by George E. Andrews
- Math310 Class Notes by Matthias Beck