Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: Elementary proof clarification.

  1. #1
    Junior Member Ahri's Avatar
    Joined
    Dec 2016
    From
    United Kingdom
    Posts
    31
    Thanks
    10

    Elementary proof clarification.

    I am reading through the proof of $$\phi(n)=\sum_{d| n}\mu(d)\frac{n}{d}$$ where $\phi $ is the Euler totient function and $\mu$ is the Mobius function.

    $$\phi(n)=\sum_{k=1}^n \left[\frac{1}{(n,k)}\right]$$$$\phi(n)=\sum_{k=1}^n \sum_{d| (n,k)} \mu(d)$$$$=\sum_{k=1}^n\sum_{\substack{d|n \\ d|k}} \mu(d)$$
    Up until this point, there are no problems, now letting $k=qd$, the next line is
    $$\sum_{d|n}\sum_{q=1}^{n/d} \mu(d)$$

    I am probably missing the obvious here, but I'm just not seeing how it got to that. Any help is appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,834
    Thanks
    1087

    Re: Elementary proof clarification.

    Since k is going from 1 to n, how many times will d divide both k and n? Well, if d divides n, then there are $\dfrac{n}{d}$ values for $k$ such that $d|k$ and $d|n$. Those values are $dq$ where $q$ goes from 1 to $\dfrac{n}{d}$. So, if we instead consider only factors $d$ of $n$, we can figure out which values for $k$ will also be divisible by $d$. It is precisely when $k=qd$.
    Thanks from Ahri
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Ahri's Avatar
    Joined
    Dec 2016
    From
    United Kingdom
    Posts
    31
    Thanks
    10

    Re: Elementary proof clarification.

    Thank you for the help SlipEternal, much appreciated.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Clarification regarding a proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jun 1st 2015, 02:59 AM
  2. Elementary matrices related proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Jan 31st 2011, 10:57 PM
  3. Elementary Analysis Proof (inequalities)
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Oct 14th 2010, 05:53 PM
  4. Help with elementary Linear Algebra proof?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Jun 7th 2009, 01:53 PM
  5. Clarification of proof
    Posted in the Geometry Forum
    Replies: 1
    Last Post: Aug 15th 2006, 11:38 AM

/mathhelpforum @mathhelpforum