Results 1 to 4 of 4

Math Help - Summation of Euler's φ-Function

  1. #1
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    Summation of Euler's φ-Function

    Euler's φ-function measures the number of positive integers equal to or less than n,
    which are relatively prime to n.
    Compute the following:
    ∑ φ(d)
    d|n

    Prove this is correct.

    The only observation I've made so far is that this must be a multiplicative function.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by elemental View Post
    Euler's φ-function measures the number of positive integers equal to or less than n,
    which are relatively prime to n.
    Compute the following:
    ∑ φ(d)
    d|n

    Prove this is correct.

    The only observation I've made so far is that this must be a multiplicative function.
    http://www.mathhelpforum.com/math-he...tml#post519966
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Let  G be a cyclic group of order  n and a be the generator .


    We have exactly  a^n = 1 , by Lagrange's Theorem , we know  o(b) | n . We now show that for a given order  d|n , the number of elements in  G of this order is \phi(d) :


    Suppose  o(b) = d , then  b^d = 1 and since it is a cyclic group , let  b = a^m , so  a^{md} = 1 and  md = nk

     m = \frac{kn}{d} we have  (k,d) = 1 , otherwise  (a^m)^{d/(k,d)} = 1 thus  o(b) \neq d .

    Moreover , to avoid repetition , let  k < d because if  k > d , by writing  k = dq + k' we can show that   a^{kn/d} = a^{k'n/d} where  0 < k' < d .

    Therefore , the number of elements of order  d is the number of numbers not exceeding d and prime to it :  \phi(d)

    Note that d is any divisor of  n and each element in the group must have its order , by equating the number of elements we obtain  \displaystyle {n = \sum_{d|n} \phi(d)}
    Last edited by simplependulum; July 8th 2010 at 12:47 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    One more proof:

    We use the fact that \phi is multiplicative function.

    If n=1

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

    If n>1, we look on the following function:

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

    since \phi is multiplicative function, easily prooved that also F is multiplicative function.

    Let n={p_1^{k_1}}{p_2^{k_2}}...{p_s^{k_s}}

    so, F(n)=F({p_1^{k_1}})F({p_2^{k_2}})...F({p_s^{k_s}})

    for every i=1,2,...,s

    F({p_i^{k_i}})=\sum_{d|{p_i^{k_i}}} \phi(d)

    =\phi(1)+\phi(p_i)+\phi(p^2_i)+...+\phi(p_i^{k_i})

    =1+(p_i-1)+(p^2_i-1)+...+(p_i^{k_i}-p_i^{k_{i-1}})=p_i^{k_i}

    Hence:

    F(n)={p_1^{k_1}}{p_2^{k_2}}...{p_s^{k_s}}=n

    F(n)=\sum_{d|n} \phi(d)=n
    Last edited by Also sprach Zarathustra; July 8th 2010 at 12:52 AM. Reason: {}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 08:29 AM
  2. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: January 12th 2010, 06:10 AM
  3. Bernoulli polynomials & Euler–Maclaurin summation
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: April 19th 2009, 09:54 AM
  4. euler phi-function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 29th 2009, 08:42 PM
  5. Help with euler-phi function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 1st 2007, 07:42 PM

Search Tags


/mathhelpforum @mathhelpforum