Mobius Inversion Formula

**tharris** · December 9th 2009, 04:08 PM

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?

**Bruno J.** · December 9th 2009, 07:25 PM

Well suppose you have a function $f$ such that $n=\sum_{d\mid n}f(d)$ . Then by the inversion formula you have $f(n)=\sum_{d \mid n}\mu(d)\frac{n}{d}$ , which is precisely $\phi(n)$ .

You actually don't even need the hypothesis that $f$ is multiplicative.

**tharris** · December 9th 2009, 08:01 PM

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?

**Bruno J.** · December 9th 2009, 08:02 PM

Sure! Apply the inversion formula to $n=\sum_{d\mid n}\phi(d)$ . What do you get?

**tharris** · December 9th 2009, 08:14 PM

I get Phi=Summation of M-function(n/d) (d) which is also equal to n? Also, how do I access the math symbols?

**Bruno J.** · December 9th 2009, 08:18 PM

To learn how to use LaTeX, click here.

If you apply the inversion formula you get $\sum_{d\mid n}\mu(d)\frac n d$ (or $\sum_{d\mid n}\mu(\frac n d)d$ , which is the same). Now compare this with above...

**tharris** · December 9th 2009, 08:23 PM

You're the best

I can't express how thankful I am that you are willing to help me.

**tharris** · December 9th 2009, 08:34 PM

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?

**PaulRS** · December 10th 2009, 04:04 AM

Actually, you do not need to know Möbius formula for this.

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

(THINK INDUCTIVELY)

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

PS: But I have to say that proving the assertion above is as long (if not longer) than proving Möbius inversion formula.

- although it seems a pretty obvious fact-

**tharris** · December 10th 2009, 12:35 PM

Thanks again

Thread: Mobius Inversion Formula

LinkBack

Thread Tools

Display

Mobius Inversion Formula

primes

Similar Math Help Forum Discussions

How to apply Mobius inversion formula

Mobius Inversion problem

Mobius Inversion Formula

Deduce from Mobius inversion formula

Mobius Inversion

Search Tags