[proofplan] We count $\varphi(n)$ as the number of integers $k \in \{1,\dots,n\}$ with $\gcd(k,n)=1$. The key input is the divisor-sum identity for the Möbius function: the sum of $\mu(d)$ over all positive divisors $d$ of an integer $m$ is $1$ if $m=1$ and $0$ otherwise. Applying this identity to $m=\gcd(k,n)$ converts the coprimality condition into a finite divisor sum, and then interchanging the finite sums reduces the formula to counting multiples of each divisor $d$ in $\{1,\dots,n\}$. [/proofplan]

[step:Prove the Möbius divisor sum detects the integer $1$] [claim:Möbius divisor sum identity] For every $m \in \mathbb{N}$, \begin{align*} \sum_{d \mid m}\mu(d)=1 \quad \text{if } m=1, \end{align*} and \begin{align*} \sum_{d \mid m}\mu(d)=0 \quad \text{if } m>1. \end{align*} [/claim] [proof] If $m=1$, the only positive divisor of $m$ is $1$, and $\mu(1)=1$, so the sum is $1$. Now suppose $m>1$. Let $p_1,\dots,p_r$ be the distinct prime divisors of $m$, where $r \in \mathbb{N}$. A divisor $d$ of $m$ contributes nonzero value $\mu(d)$ exactly when $d$ is squarefree. Since every squarefree divisor of $m$ is divisible only by distinct primes among $p_1,\dots,p_r$, and each product of a subset of these primes divides $m$, the contributing divisors are precisely the products of primes indexed by subsets $S \subseteq \{1,\dots,r\}$. For such a subset $S$, define the positive integer \begin{align*} d_S=\prod_{i \in S} p_i, \end{align*} with the convention $d_{\varnothing}=1$. Then $\mu(d_S)=(-1)^{|S|}$, and hence \begin{align*} \sum_{d \mid m}\mu(d)=\sum_{S \subseteq \{1,\dots,r\}}(-1)^{|S|}. \end{align*} Grouping subsets by their cardinality gives \begin{align*} \sum_{S \subseteq \{1,\dots,r\}}(-1)^{|S|}=\sum_{j=0}^{r}\binom{r}{j}(-1)^j. \end{align*} By the [binomial theorem](/theorems/750) applied to $(1-1)^r$, this last sum is $0$. Therefore the divisor sum is $0$ for every $m>1$. [/proof] [/step]

[step:Rewrite the coprimality indicator as a Möbius divisor sum]Fix $n \in \mathbb{N}$. For each $k \in \{1,\dots,n\}$, define the integer \begin{align*} g_k=\gcd(k,n). \end{align*} Also define the indicator function \begin{align*} \mathbb{1}_{\{\gcd(\cdot,n)=1\}}: \{1,\dots,n\} &\to \{0,1\} \end{align*} by setting $\mathbb{1}_{\{\gcd(\cdot,n)=1\}}(k)=1$ when $\gcd(k,n)=1$ and $\mathbb{1}_{\{\gcd(\cdot,n)=1\}}(k)=0$ otherwise. We write this value as $\mathbb{1}_{\{\gcd(k,n)=1\}}$. By the Möbius divisor sum identity applied to $m=g_k$, \begin{align*} \mathbb{1}_{\{\gcd(k,n)=1\}}=\sum_{d \mid g_k}\mu(d). \end{align*}[/step]

[guided]Fix $n \in \mathbb{N}$. The goal is to replace the condition $\gcd(k,n)=1$ by an algebraic expression that can be summed. For each $k \in \{1,\dots,n\}$, define \begin{align*} g_k=\gcd(k,n). \end{align*} Define the indicator function \begin{align*} \mathbb{1}_{\{\gcd(\cdot,n)=1\}}: \{1,\dots,n\} &\to \{0,1\} \end{align*} by setting $\mathbb{1}_{\{\gcd(\cdot,n)=1\}}(k)=1$ when $\gcd(k,n)=1$ and $\mathbb{1}_{\{\gcd(\cdot,n)=1\}}(k)=0$ otherwise; its value at $k$ is written $\mathbb{1}_{\{\gcd(k,n)=1\}}$. The integer $g_k$ is positive, so the Möbius divisor sum identity applies to it. That identity says that \begin{align*} \sum_{d \mid g_k}\mu(d)=1 \end{align*} exactly when $g_k=1$, and that \begin{align*} \sum_{d \mid g_k}\mu(d)=0 \end{align*} when $g_k>1$. Since $g_k=1$ is precisely the condition $\gcd(k,n)=1$, this gives \begin{align*} \mathbb{1}_{\{\gcd(k,n)=1\}}=\sum_{d \mid g_k}\mu(d). \end{align*} This is the mechanism of the proof: the Möbius function turns the coprimality condition into a divisor sum over common divisors.[/guided]

[step:Sum over $k$ and interchange the finite sums] By the definition of Euler's totient function, \begin{align*} \varphi(n)=\sum_{k=1}^{n}\mathbb{1}_{\{\gcd(k,n)=1\}}. \end{align*} Using the previous step, \begin{align*} \varphi(n)=\sum_{k=1}^{n}\sum_{d \mid \gcd(k,n)}\mu(d). \end{align*} The condition $d \mid \gcd(k,n)$ is equivalent to the pair of conditions $d \mid n$ and $d \mid k$. Since all sums are finite, we may reorder the summation. Here $\#A$ denotes the cardinality of a finite set $A$. Therefore \begin{align*} \varphi(n)=\sum_{d \mid n}\mu(d)\,\#\{k \in \{1,\dots,n\}: d \mid k\}. \end{align*} [/step]

[step:Count the multiples of each divisor and conclude the formula] Let $d$ be a positive divisor of $n$. Since $d \mid n$, there exists a unique integer $q_d \in \mathbb{N}$ such that \begin{align*} n=dq_d. \end{align*} The integers $k \in \{1,\dots,n\}$ divisible by $d$ are exactly \begin{align*} d,2d,\dots,q_d d. \end{align*} Hence \begin{align*} \#\{k \in \{1,\dots,n\}: d \mid k\}=q_d=\frac{n}{d}. \end{align*} Substituting this count into the formula from the previous step gives \begin{align*} \varphi(n)=\sum_{d \mid n}\mu(d)\frac{n}{d}. \end{align*} Since $n \in \mathbb{N}$ was arbitrary, the identity holds for every positive integer $n$. [/step]