[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*}
[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]
[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]
