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?

  • 3
    $\begingroup$ As far as the intuition goes, yes, this is the right idea. $\endgroup$ – Chris Jun 17 '17 at 5:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jun 17 '17 at 5:06
  • $\begingroup$ Yes, this is a direct application of the inclusion-exclusion principle. $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.