# Prove $\sum_{d\mid n}\mu(d)=[\frac{1}{n}]$

I'm reading a direct proof for mobius inversion theorem but I don’t know how the writer make the assumption that $$\sum_{d\mid n}\mu(d)=\left[\frac{1}{n}\right]$$

Can someone please explain and prove this?

• There are proofs on Wikipedia Nov 18, 2020 at 17:03

Observe that

$$\left\lfloor\frac1n\right\rfloor=\begin{cases} 1,&\text{if }n=1\\ 0,&\text{if }n>0\,, \end{cases}$$

so this is just a fancy way of saying that

$$\sum_{d\mid n}\mu(d)=\begin{cases} 1,&\text{if }n=1\\ 0,&\text{if }n>0\,. \end{cases}\tag{1}$$

By definition $$\mu(1)=1$$, so $$(1)$$ holds for $$n=1$$. If $$p$$ is any prime,

\begin{align*} \sum_{d\mid p^k}\mu(d)&=\sum_{i=0}^k\mu(p^i)\\ &=\mu(1)+\mu(p)+\sum_{i=2}^k\mu(p^i)\\ &=1+(-1)+0\\ &=0\,. \end{align*}

The result now follows from the fact that $$\mu$$ is multiplicative.

When $$n=1$$ we have $$\sum_{ d|n} \mu(d)=\mu(1)=1$$.

When $$n>1$$, then write $$n=p_1^{a_1}p_2^{a_2} \dots p_k^{a_k}$$, we get \begin{align*} \sum_{ d|n} \mu(d)&=\sum_{ 0 \leq b_i \leq a_i} \mu(p_1^{b_1}p_2^{b_2} \dots p_k^{b_k})\\ &=\mu(1)+\mu(p_1)+\dots \mu(p_n)+\mu(p_1p_2)\dots \mu(p_{n-1}p_n)+\dots\mu(p_1 \dots p_n)\\ &=1(-1)^0+{n \choose 1}(-1)^1+{n \choose 2}(-1)^2+{n \choose 3}(-1)^3+ \dots {n \choose n}(-1)^n \\ &=(1-1)^n \\ &=0. \end{align*} Hence $$\sum_{ d|n} \mu(d)=\begin{cases} 1,&\text{if }n=1\\ 0,&\text{if }n>0\ \end{cases}=\left\lfloor\frac1n\right\rfloor$$

This proves your result. Note that this proof doesn't assume the multiplicative property.