# Mobius Inversion Formula

• Dec 9th 2009, 04:08 PM
tharris
Mobius Inversion Formula
Prove that if f is multiplicative and the sum of f(d) (where the sum extends over all positive divisors of n) = n for all n, then f = Phi ( where the phi function is defined as the the number of positive integers not exceeding n that are relatively prime to n). As related to the Mobius Inversion Formula.
Can anyone get me going on this proof?
• Dec 9th 2009, 07:25 PM
Bruno J.
Well suppose you have a function $\displaystyle f$ such that $\displaystyle n=\sum_{d\mid n}f(d)$. Then by the inversion formula you have $\displaystyle f(n)=\sum_{d \mid n}\mu(d)\frac{n}{d}$, which is precisely $\displaystyle \phi(n)$.

You actually don't even need the hypothesis that $\displaystyle f$ is multiplicative.
• Dec 9th 2009, 08:01 PM
tharris
I don't see how it is the same as phi(n). I understand the mechanics of the mobius inversion formula - but I'm not seeing the relationship to the phi function. Can you help me connect them?
• Dec 9th 2009, 08:02 PM
Bruno J.
Sure! Apply the inversion formula to $\displaystyle n=\sum_{d\mid n}\phi(d)$. What do you get? (Giggle)
• Dec 9th 2009, 08:14 PM
tharris
I get Phi=Summation of M-function(n/d) (d) which is also equal to n? Also, how do I access the math symbols?
• Dec 9th 2009, 08:18 PM
Bruno J.

If you apply the inversion formula you get $\displaystyle \sum_{d\mid n}\mu(d)\frac n d$ (or $\displaystyle \sum_{d\mid n}\mu(\frac n d)d$, which is the same). Now compare this with above...
• Dec 9th 2009, 08:23 PM
tharris
You're the best(Rofl) I can't express how thankful I am that you are willing to help me.
• Dec 9th 2009, 08:34 PM
tharris
primes
Hi. I'm working on a few other questions as well. If you be so kind, I'd appreciate your input on this problem.
Suppose n>0, p/n, p is prime, p^2/n, Show that there exists integers a and b such that n=a^3b^2.
Now, it seems to me that all exponents of the prime factors of n have to be at least power of 2 which means that the odd exponents have power at least 3 which would satisfy the above statement. But I'm not sure how to show this symbolically - perhaps the explanation is enough?
• Dec 10th 2009, 04:04 AM
PaulRS
Actually, you do not need to know Möbius formula for this.

If you think of it, having: $\displaystyle \sum_{d|n}f(d)=g(n)$ for a given function $\displaystyle g$, determines $\displaystyle f$ for all positive integers $\displaystyle n$. (In fact $\displaystyle f(n)$ is linear combination of $\displaystyle g(d)$ for $\displaystyle d|n$)

(THINK INDUCTIVELY)

Now since on the other post we proved that $\displaystyle \phi$ satisfies $\displaystyle \sum_{d|n}\phi(d)=n$ it follows that $\displaystyle f(n)=\phi(n)$ for all positive integers $\displaystyle n$.

PS: But I have to say that proving the assertion above is as long (if not longer) than proving Möbius inversion formula. (Rofl) - although it seems a pretty obvious fact-
• Dec 10th 2009, 12:35 PM
tharris
Thanks again(Rock)