[proofplan] We first prove the divisor-sum identity by partitioning the integers $1,\dots,n$ according to their greatest common divisor with $n$. Each part with common divisor $m$ is counted by reduced residues modulo $n/m$, giving $\varphi(n/m)$ elements. Then we show that the constant-one arithmetic function has Dirichlet inverse $\mu$, so convolving the divisor-sum identity with $\mu$ gives $\varphi = \operatorname{id} * \mu$. [/proofplan] [step:Partition the integers from $1$ to $n$ by their greatest common divisor with $n$] Fix $n \in \mathbb{N}$. For each positive divisor $m$ of $n$, define \begin{align*} A_m := \{a \in \{1,\dots,n\} : \gcd(a,n) = m\}. \end{align*} The sets $A_m$, as $m$ ranges over the positive divisors of $n$, are pairwise disjoint and their union is $\{1,\dots,n\}$, because every $a \in \{1,\dots,n\}$ has a uniquely determined greatest common divisor $\gcd(a,n)$, and this integer divides $n$. Therefore \begin{align*} n = \sum_{m \mid n} |A_m|. \end{align*} [guided] Fix $n \in \mathbb{N}$. We want to count the $n$ integers $1,\dots,n$ in a way that produces Euler totients. The natural invariant attached to an integer $a$ is its common divisor with $n$, so for every positive divisor $m$ of $n$ we define \begin{align*} A_m := \{a \in \{1,\dots,n\} : \gcd(a,n) = m\}. \end{align*} These sets do not overlap: if $a \in A_m \cap A_{m'}$, then $\gcd(a,n)=m$ and $\gcd(a,n)=m'$, hence $m=m'$. They also cover all of $\{1,\dots,n\}$, since every integer $a$ in this range has a greatest common divisor with $n$, and that greatest common divisor is a positive divisor of $n$. Thus the cardinalities add: \begin{align*} n = |\{1,\dots,n\}| = \sum_{m \mid n} |A_m|. \end{align*} This reduces the desired identity to computing the size of each $A_m$. [/guided] [/step] [step:Count each greatest-common-divisor class by reduced residues] For each divisor $m$ of $n$, define \begin{align*} B_m := \left\{b \in \left\{1,\dots,\frac{n}{m}\right\} : \gcd\left(b,\frac{n}{m}\right)=1\right\}. \end{align*} Define the map \begin{align*} T_m: B_m &\to A_m \\ b &\mapsto mb. \end{align*} If $b \in B_m$, then $1 \le mb \le n$ and \begin{align*} \gcd(mb,n) = m\gcd\left(b,\frac{n}{m}\right)=m, \end{align*} so $T_m(b) \in A_m$. Conversely, if $a \in A_m$, then $m \mid a$, so $a=mb$ for a unique $b \in \{1,\dots,n/m\}$, and \begin{align*} m = \gcd(a,n) = \gcd\left(mb,m\frac{n}{m}\right) = m\gcd\left(b,\frac{n}{m}\right). \end{align*} Cancelling $m$ gives $\gcd(b,n/m)=1$, so $b \in B_m$. Hence $T_m$ is a bijection and \begin{align*} |A_m| = |B_m| = \varphi\left(\frac{n}{m}\right). \end{align*} [guided] Fix a divisor $m$ of $n$. We now count the integers $a$ whose common divisor with $n$ is exactly $m$. Dividing such an $a$ by $m$ should leave an integer relatively prime to $n/m$, so define \begin{align*} B_m := \left\{b \in \left\{1,\dots,\frac{n}{m}\right\} : \gcd\left(b,\frac{n}{m}\right)=1\right\}. \end{align*} This is precisely the set counted by $\varphi(n/m)$. Define \begin{align*} T_m: B_m &\to A_m \\ b &\mapsto mb. \end{align*} First we check that $T_m$ is well-defined. If $b \in B_m$, then $1 \le b \le n/m$, so $1 \le mb \le n$. Also, \begin{align*} \gcd(mb,n) = \gcd\left(mb,m\frac{n}{m}\right) = m\gcd\left(b,\frac{n}{m}\right) = m. \end{align*} Thus $mb \in A_m$. Now take any $a \in A_m$. Since $\gcd(a,n)=m$, the integer $m$ divides $a$, so there is a unique integer $b$ with $a=mb$. Because $1 \le a \le n$, this $b$ satisfies $1 \le b \le n/m$. Moreover, \begin{align*} m = \gcd(a,n) = \gcd\left(mb,m\frac{n}{m}\right) = m\gcd\left(b,\frac{n}{m}\right). \end{align*} Dividing by $m$ gives $\gcd(b,n/m)=1$, so $b \in B_m$. This proves that every element of $A_m$ comes from exactly one element of $B_m$, and therefore $T_m$ is a bijection. Hence \begin{align*} |A_m| = |B_m| = \varphi\left(\frac{n}{m}\right). \end{align*} [/guided] [/step] [step:Sum the classes to obtain the divisor-sum identity] Combining the preceding two steps gives \begin{align*} n = \sum_{m \mid n} |A_m| = \sum_{m \mid n} \varphi\left(\frac{n}{m}\right). \end{align*} As $m$ ranges over the positive divisors of $n$, the integer $d := n/m$ also ranges over the positive divisors of $n$. Therefore \begin{align*} n = \sum_{d \mid n} \varphi(d). \end{align*} This proves the divisor-sum identity for every $n \in \mathbb{N}$. [/step] [step:Identify the Mobius function as the Dirichlet inverse of the constant-one function] Let $\mathbb{1}: \mathbb{N} \to \mathbb{N}$ denote the constant-one arithmetic function, $\mathbb{1}(n)=1$. We claim that \begin{align*} \mathbb{1} * \mu = \varepsilon, \end{align*} where $\varepsilon: \mathbb{N} \to \{0,1\}$ is the Dirichlet identity function defined by $\varepsilon(1)=1$ and $\varepsilon(n)=0$ for $n>1$. Indeed, for $n=1$, \begin{align*} (\mathbb{1} * \mu)(1)=\mu(1)=1. \end{align*} For $n>1$, let $p_1,\dots,p_r$ be the distinct prime divisors of $n$, where $r \in \mathbb{N}$. Only squarefree divisors contribute to the sum defining $\mu$, so \begin{align*} (\mathbb{1} * \mu)(n) = \sum_{d \mid n} \mu(d) = \sum_{S \subset \{1,\dots,r\}} (-1)^{|S|} = (1-1)^r = 0. \end{align*} Thus $\mathbb{1} * \mu=\varepsilon$. [guided] Let $\mathbb{1}: \mathbb{N} \to \mathbb{N}$ be the arithmetic function with $\mathbb{1}(n)=1$ for all $n$, and let $\varepsilon: \mathbb{N} \to \{0,1\}$ be the Dirichlet identity function, defined by $\varepsilon(1)=1$ and $\varepsilon(n)=0$ for $n>1$. We prove that $\mu$ is the Dirichlet inverse of $\mathbb{1}$, meaning \begin{align*} \mathbb{1} * \mu = \varepsilon. \end{align*} At $n=1$, the only positive divisor is $1$, and by the definition of the Mobius function $\mu(1)=1$. Hence \begin{align*} (\mathbb{1} * \mu)(1)=\sum_{d \mid 1}\mathbb{1}(d)\mu\left(\frac{1}{d}\right)=\mu(1)=1. \end{align*} Now suppose $n>1$. Let $p_1,\dots,p_r$ be the distinct prime divisors of $n$. Since $n>1$, we have $r \ge 1$. In the divisor sum \begin{align*} (\mathbb{1} * \mu)(n)=\sum_{d \mid n}\mu(d), \end{align*} any divisor $d$ divisible by the square of a prime has $\mu(d)=0$. Thus only squarefree divisors matter. Each squarefree divisor of $n$ is uniquely of the form \begin{align*} d_S := \prod_{i \in S} p_i \end{align*} for a subset $S \subset \{1,\dots,r\}$, and for this divisor $\mu(d_S)=(-1)^{|S|}$. Therefore \begin{align*} \sum_{d \mid n}\mu(d) = \sum_{S \subset \{1,\dots,r\}} (-1)^{|S|} = \sum_{k=0}^r \binom{r}{k}(-1)^k = (1-1)^r = 0. \end{align*} This proves $(\mathbb{1} * \mu)(n)=0$ for all $n>1$, and therefore $\mathbb{1} * \mu=\varepsilon$. [/guided] [/step] [step:Convolve the divisor-sum identity with the Mobius function] The divisor-sum identity says exactly that \begin{align*} \mathbb{1} * \varphi = \operatorname{id}. \end{align*} Dirichlet convolution is commutative and associative for arithmetic functions, because all sums are finite divisor sums. Convolving both sides with $\mu$ gives \begin{align*} \mu * (\mathbb{1} * \varphi) = \mu * \operatorname{id}. \end{align*} By associativity, commutativity, and $\mu * \mathbb{1}=\varepsilon$, \begin{align*} \mu * (\mathbb{1} * \varphi) = (\mu * \mathbb{1}) * \varphi = \varepsilon * \varphi = \varphi. \end{align*} Also, by commutativity, \begin{align*} \mu * \operatorname{id} = \operatorname{id} * \mu. \end{align*} Hence \begin{align*} \varphi = \operatorname{id} * \mu. \end{align*} Together with the divisor-sum identity already proved, this establishes both equivalent formulations of the theorem. [/step]