Can anybody help me simplify this expression using Mobius Inversion Formula or any other result in order to calculate F(3500) in a simple way?? $$F(n)=\sum_{d\mid n} \mu(d)d$$

  • 1
    $\begingroup$ Hint: $\mu(n)n$ is multiplicative, hence so is $F(n).$ $\endgroup$ – Thomas Andrews Apr 8 at 17:48
  • $\begingroup$ Thank you very much for your hint. This is the key of the exercise (It was not about Mobius Inversion) !! $\endgroup$ – Luis Gimeno Sotelo Apr 8 at 17:59

It is the product $$f(n)=(1-p_1)(1-p_2)\cdots(1-p_k)$$ where the $p_i$ are the distinct prime divisors of $d.$

This is because $g(n)=\mu(n)n$ is multiplicative, and hence so is $F,$ and $F(p^k)=1-p$ for prime $p.$

In your case, $3500$ has prime divisors $2,5,$ and $7$. So:


You could write it as $F(n)=n\sum_{d\mid n} \mu(d)\frac{1}{n/d}.$ Then you get, by Möbius inversion: $$\frac{1}{n}=\sum_{d\mid n}\frac{F(d)}{d}$$


$$1=\sum_{d\mid n}\frac{n}{d}F(d)$$

That won't help you compute $F$ much however.


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.