Results 1 to 10 of 10

Math Help - Mobius Inversion Formula

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    19

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2009
    Posts
    19
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Sure! Apply the inversion formula to n=\sum_{d\mid n}\phi(d). What do you get?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2009
    Posts
    19
    I get Phi=Summation of M-function(n/d) (d) which is also equal to n? Also, how do I access the math symbols?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2009
    Posts
    19
    You're the best I can't express how thankful I am that you are willing to help me.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Dec 2009
    Posts
    19

    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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-
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Dec 2009
    Posts
    19
    Thanks again
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How to apply Mobius inversion formula
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2012, 10:16 AM
  2. Mobius Inversion problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 31st 2010, 08:36 PM
  3. Mobius Inversion Formula
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 26th 2010, 09:46 AM
  4. Deduce from Mobius inversion formula
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 15th 2008, 04:40 PM
  5. Mobius Inversion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 26th 2008, 05:42 PM

Search Tags


/mathhelpforum @mathhelpforum