Results 1 to 4 of 4

Thread: Summation of Euler's φ-Function

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

    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 $\displaystyle G $ be a cyclic group of order $\displaystyle n $ and $\displaystyle a $ be the generator .


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


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

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

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

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

    Note that $\displaystyle d $ is any divisor of $\displaystyle n $ and each element in the group must have its order , by equating the number of elements we obtain $\displaystyle \displaystyle {n = \sum_{d|n} \phi(d)} $
    Last edited by simplependulum; Jul 7th 2010 at 11:47 PM.
    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 $\displaystyle \phi$ is multiplicative function.

    If $\displaystyle n=1$

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

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

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

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

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

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

    for every $\displaystyle i=1,2,...,s$

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

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

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

    Hence:

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

    $\displaystyle F(n)=\sum_{d|n} \phi(d)=n$
    Last edited by Also sprach Zarathustra; Jul 7th 2010 at 11:52 PM. 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, 07:29 AM
  2. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: Jan 12th 2010, 05:10 AM
  3. Bernoulli polynomials & Euler–Maclaurin summation
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Apr 19th 2009, 08:54 AM
  4. euler phi-function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 29th 2009, 07:42 PM
  5. Help with euler-phi function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 1st 2007, 06:42 PM

Search Tags


/mathhelpforum @mathhelpforum