Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to find some work done on the following: $$\sum_{d \vert n}\frac{2^{\omega(d)}}{d}\mu(d)$$ where $\omega(d)$ is the number of distinct prime factors of $d$ and $\mu$ is the Möbius function. I saw something about $$\sum_{d \vert n}\frac{\mu(d)}{d}=\phi(n)/n$$ (where $\phi$ is the Euler phi function) on planetmath, but I'm not entirely certain how to use it. Does anyone know of any work done on the first sum?

share|cite|improve this question
Cross posted at MO... – draks ... Jul 15 '12 at 18:36

Note that since $\omega$ is additive and $\mu$ is multiplicative, the function $\sum_{d \, | \, n} \frac{ 2^{\omega(d)} \mu(d) }{d}$ is multiplicative, so it suffices to compute it at prime powers.

At prime powers, one easily computes $1 - \frac 2p$, since $$ \sum_{d \, | \, p^{\alpha}} \frac{ 2^{\omega(d)} \mu(d) }d = \sum_{i=0}^{\alpha} \frac{ 2^{\omega(p^i)} \mu(p^i) }{p^i} = 1 - \frac 2p $$ so that $$ \sum_{d \, | \, n} \frac{ 2^{\omega(d)} \mu(d) }{d} = \prod_{p \, | \, n} \left( 1 - \frac 2p \right). $$

Hope that helps,

share|cite|improve this answer

Let $n=p_1^{a_1}\cdots p_k^{a_k}$. We can prove that $$\sum_{d|n}\frac{m^{\omega(d)}}{d}\mu(d)=\prod_{i=1}^k\left(1-\frac{m}{p_i}\right)$$ (notice that for $m=1$ this is $\varphi(n)/n$). The proof is easy, just check the corresponding coefficients of $m^{r}$ on both sides.

Indeed, there is the well-known identity $$\prod_{i=1}^k (1+tx_i)=\sum_{r=1}^k t^r e_r(x_1,\dots,x_k)$$ where the $e_r$'s are the elementary symmetric polynomials. If we let $S(n)$ denote the squarefree part of $n$, then by putting $x_i=\frac{1}{p_i}$ we get $$\sum_{d|S(n)}\frac{t^{\omega(d)}}{d}=\sum_{r=1}^k t^r e_r(\frac{1}{p_1},\dots,\frac{1}{p_k})=\prod_{i=1}^k\left(1+\frac{t}{p_i}\right)$$

Now to get your identity just use $t=-m$, and the fact that $\mu(d)=(-1)^{\omega(d)}$ when $d$ is squarefree. For $t=-2$ we get $$\left(1-\frac{2}{p_1}\right)\cdots\left(1-\frac{2}{p_k}\right)$$ which is always non-negative (it is $=0$ only when $n$ is even).

share|cite|improve this answer
Not bad, it's a pretty interesting way of proving this. +1 – Patrick Da Silva Aug 30 '11 at 4:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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