# Intuition behind $\phi(n) = \sum\limits_{d\mid n}\mu(d)\frac{n}{d}$

I would like to know if the following intuition is valid:

Suppose $n = \prod\limits_{i=1}^k p_i^{a_i}$

The only divisors we care about are those that have distinct prime factors (with no squares).

So $\sum\limits_{d\mid n}\mu(d)\frac{n}{d} = n - \sum\limits_{i=1}^k\frac{n}{p_i} + \sum\limits_{i=1,j= 1, i<j}^k\frac{n}{p_ip_j} - \sum\limits_{i=1,j= 1,m=1,i<j<m}^k\frac{n}{p_ip_jp_m} \ldots$

Essentially this is using PIE to find numbers that are relatively prime to n. Hence I claim that this is equal to $\phi(n)$.

Is this correct?

• As far as the intuition goes, yes, this is the right idea. – Chris Jun 17 '17 at 5:01
• Yes, alternatively, you can use the Chinese remainder theorem to show that $\phi(n)=n(1-1/p_1)(1-1/p_2)\cdots(1-1/p_n)$, which then intuitively expands as above. – Thomas Andrews Jun 17 '17 at 5:06
• Yes, this is a direct application of the inclusion-exclusion principle. – reuns Jun 17 '17 at 12:17

Yes, this is a correct and direct application of the inclusion-exclusion principle.

To be more explicit, without looking at the prime factorization :

$$\phi(n) = \sum_{\substack{m \le n\\ gcd(m,n)=1} }m^{0}=\sum_{m \le n} m^0 \sum_{d \ | \ gcd(m,n)} \mu(d) = \sum_d \mu(d) \sum_{\substack{m \le n\\ d \ |\ gcd(m,n)}}m^{0} = \sum_{d | n} \mu(d) \frac{n}{d}$$ Then you prove that this function $\mu(n)$ having the property that $\sum_{d | n} \mu(d) = \begin{cases}1 \text{ if } n = 1,\\ 0 \text{ otherwise } \end{cases}$ is $$\mu(n) = \begin{cases}\prod_{p | n} (-1) \text{ if } n \text{ is square-free },\\ 0 \text{ otherwise } \end{cases}$$ From which what you wrote follows

You are just re-discovering Möbius inversion formula.
In terms of formal Dirichlet's series, by exploiting Euler's product we have

$$\sum_{n\geq 1}\frac{\varphi(n)}{n^s} = \prod_{p}\left(1+\frac{\varphi(p)}{p^s}+\frac{\varphi(p^2)}{p^{2s}}+\ldots\right)=\prod_{p}\frac{p^s-1}{p^s-p}\tag{1}$$ hence: $$\sum_{n\geq 1}\frac{\varphi(n)}{n^s} = \prod_{p}\frac{1-\frac{1}{p^s}}{1-\frac{1}{p^{s-1}}}=\frac{\zeta(s-1)}{\zeta(s)}\tag{2}$$ as well as: $$\sum_{n\geq 1}\frac{\mu(n)}{n^s} = \prod_{p}\left(1-\frac{1}{p^s}\right) = \frac{1}{\zeta(s)} \tag{3}$$ hence by $(2)$ and $(3)$ it follows that: $$\sum_{n\geq 1}\frac{\varphi(n)}{n^s} = \left(\sum_{n\geq 1}\frac{n}{n^s}\right)\cdot\left(\sum_{n\geq 1}\frac{\mu(n)}{n^s}\right)=\sum_{n\geq 1}\frac{1}{n^s}\sum_{d\mid n}\mu(d)\frac{n}{d}\tag{4}$$ hence $\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}$ as wanted.

Alternative proof: the cyclotomic polynomial $\Phi_n(x)$ is the minimal polynomial of a primitive $n$-th root of unity, and by the inclusion-exclusion principle $$\Phi_n(x) = \prod_{d\mid n}\left(x^{\frac{n}{d}}-1\right)^{\mu(d)}\tag{5}$$ so $\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}$ follows by comparing the degrees of the LHS and the RHS in $(5)$.

since $\mu(n)$ and $\frac1n$ are multiplicative functions, so is the convolution $$f(n) =\sum_{d|n}\mu(d)\frac{n}d$$ it is straightforward that $(k \ge 1)$: $$f(p^k) = p^k \bigg(1-\frac1p \bigg) =\phi(p^k)$$ and from this: $$\phi(n)=\phi(p_1^{k_1}p_2^{k_2}\dots) = \prod_{j}p_j^{k_j} \bigg(1-\frac1p_j \bigg) \\ = n \prod_{j}\bigg(1-\frac1p_j \bigg)$$ whose terms when expanded correspond to those you obtain using the inclusion-exclusion principle on subsets of the set of primes dividing $n$.

contrariwise since every element of the additive group $Z_n$ is a generator of exactly one of the (cyclic) subgroups of $Z_n$, whose orders are the divisors of $n$, we have: $$n = \sum_{d|n} \phi(d)$$ so by Mobius inversion: $$\phi(n) = \mu * id (n) = \sum_{d|n}\mu(d)\frac{n}{d}$$ where $id(n)=n$ for all relevant values of its argument