Results 1 to 6 of 6

Math Help - Euler's totient function Proof

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    224

    Euler's totient function Proof

    Where n is an integer and d is a positive divisor of n and \phi is the Euler Totient function, how do we prove that:

    \sum_{d|n} \phi(d) = n ?

    I have absolutely no idea how to approach this problem, any help to get me started is very much appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The 'direct proof' is a little 'efforts spending'. A confortable alternative is to read...

    Möbius Inversion Formula -- from Wolfram MathWorld

    ...where the 'Moebius inversion pair formula' is illustrated...

    \displaystyle g(n)= \sum_{d|n} f(d)

    \displaystyle f(n)= \sum_{d|n} \mu(d)\ g(\frac{n}{d}) (1)

    Here \mu(*) is the 'Moebius function'. Of course the (1) can be apply 'from top to bottom' or 'from bottom to top'... using the last option You derive that...

    \displaystyle \varphi(n)= \sum_{d|n} \mu(d)\ \frac{n}{d} \implies n= \sum_{d|n} \varphi (d) (2)

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    chisigma has provided a "advanced" proof, here is a "elementary" proof:
    consider the set {1,2,3,...,n}, there are n elements in it, for each element k , there is exactly one divisor d of n such that (n,k)=d. so the collection of all subsets \{k|(n,k)=d\} where d divides n, forms a partition of {1,2,...,3}. for each d, the subset \{k|(n,k)=d\} contains \phi(n/d) elements.
    as d run over all divisors of n, n/d run over all divisors of n, the identity follows.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by demode View Post
    Where n is an integer and d is a positive divisor of n and \phi is the Euler Totient function, how do we prove that:

    \sum_{d|n} \phi(d) = n ?

    I have absolutely no idea how to approach this problem, any help to get me started is very much appreciated.

    An alternative idea to the two already given, if you know some group theory:

    Look at the cyclic group C_n of order n , and then use that :

    1) It has a unique (cyclic, also) group of order d, for any divisor d of n ;

    2) A cyclic group of order k has exactly \phi(k) generators.

    Put the above together and voila!

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2009
    Posts
    224
    Thanks Tonio and Shanks. I know group theory so Tonio's suggestion was also pretty straightforward. Also as a related question, how should I go about calculating the cardinality of the set \{ k| gcd(k,n)=d \}?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Quote Originally Posted by demode View Post
    Thanks Tonio and Shanks. I know group theory so Tonio's suggestion was also pretty straightforward. Also as a related question, how should I go about calculating the cardinality of the set \{ k| gcd(k,n)=d \}?
    gcd(k,n)=d implies
    (1) k and n are both divisible by d;
    (2) k/d and n/d are relatively prime.
    so combine (1) and (2), we have
    the cardinality of the set \{ k| gcd(k,n)=d \} equals to the cardinality of the set \{ k| gcd(k/d,n/d)=1 \}, that is \phi(n/d).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 5th 2010, 01:04 AM
  2. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 06:11 PM
  3. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2009, 07:16 PM
  4. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 08:53 PM
  5. Euler totient function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 25th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum