In order to show this, we will take the set \(\{1,2,3,\ldots,n\}\) and partition it into subsets of numbers that each have the same \(\gcd\) with \(n\text{.}\) If we can show there are \(\phi(d)\) numbers having each possible \(\gcd\text{,}\) then that totals up to \(n\text{.}\)
Indeed, the only possibilities for greatest common divisor with \(n\) are the \(k\) various divisors \(\{d_i\}_{i=1}^k\) of \(n\text{,}\) so that each subset corresponds to one of these divisors. Our subsets then look like
\begin{equation*}
\{a\in\mathbb{Z}\mid 0\leq a\leq n-1,\; \gcd(a,n)=1=d_1\},\ldots
\end{equation*}
\begin{equation*}
\{a\in\mathbb{Z}\mid 0\leq a\leq n-1,\; \gcd(a,n)=d_k\}\text{.}
\end{equation*}
Let’s look at these sets more carefully. Each one consists of numbers sharing divisor \(d_i\) with \(n\text{.}\) So, if we wanted to, we could divide all the numbers in the \(i\)th set
\begin{equation*}
\{a\in\mathbb{Z}\mid 0\leq a\leq n-1,\;\gcd(a,n)=d_i\}
\end{equation*}
by their common factor \(d_i\text{.}\)
That new set will be the set of positive numbers \(b\leq \frac{n}{d_i}\) also coprime to \(\frac{n}{d_i}\text{.}\) So the size of the subset of numbers having gcd \(d_i\) with \(n\) is the same as the number of these \(b\) coprime to \(\frac{n}{d_i}\text{.}\)
More precisely, if we look at all the original subsets in question, they have the same sizes as the following sets:
\begin{equation*}
\{b\in\mathbb{Z}\mid 1\leq b\leq n/1,\; \gcd(b,n/1)=1\},\ldots
\end{equation*}
\begin{equation*}
\{b\in\mathbb{Z}\mid 1\leq b\leq n/n,\; \gcd(b,n/n)=\gcd(b,1)=1\}\text{.}
\end{equation*}
These new sets \(\{b\in\mathbb{Z}\mid 1\leq b\leq n/d_i,\; \gcd(b,n/d_i)=1\}\) themselves are different from before (and possible not disjoint). But their sizes (or cardinalities) are the same as before, and the old sets were all disjoint, so we conclude that
\begin{equation*}
n=\phi(n)+\phi(n/d_1)+\phi(n/d_2)+\cdots+\phi(1)\text{.}
\end{equation*}
But the set of numbers \(\frac{n}{d_i}\) for all divisors \(d_i\) of \(n\) is also the set of all divisors of \(n\text{,}\) so we can rewrite the sum as desired!
\begin{equation*}
n=\sum_{d\mid n} \phi(d)
\end{equation*}