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?

  • $\begingroup$ There are proofs on Wikipedia $\endgroup$
    – player3236
    Nov 18, 2020 at 17:03

2 Answers 2


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.


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.