Results 1 to 3 of 3

Math Help - Euler's Totient Function

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    Euler's Totient Function

    Show there exists  C>0 such that  n^{1-\epsilon}<\varphi(n) \;\; \forall \; n>2 , where  \epsilon = C\log\log n/\log n .
    Last edited by chiph588@; July 16th 2010 at 07:13 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Does that work for n = 2 ? ....

    Remember that \tfrac{n}{\phi(n)}<\zeta(2)\cdot \left(\tfrac{\sigma(n)}{n}\right) ( see here )

    Now \tfrac{\sigma(n)}{n} = \sum_{d|n}\left(\tfrac{1}{d}\right) \leq H_n = 1 + \tfrac{1}{2} + ... + \tfrac{1}{n} \leq \log(n) + 1

    Thus \tfrac{n}{\phi(n)}<\zeta(2)\cdot \left(\log(n) + 1\right) < \left(\log(3)\right)^{k-1} \cdot \log( n) \leq \left( \log( n) \right)^k if we pick k large enough (since \log( 3) > 1 )

    Then we'd have \tfrac{n}{\phi(n)} < \left( \log( n) \right)^k = n^{k\cdot \left(\tfrac{\log\log n}{\log n}\right)} for n > 2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by PaulRS View Post
    Does that work for n = 2 ? ....

    Remember that \tfrac{n}{\phi(n)}<\zeta(2)\cdot \left(\tfrac{\sigma(n)}{n}\right) ( see here )

    Now \tfrac{\sigma(n)}{n} = \sum_{d|n}\left(\tfrac{1}{d}\right) \leq H_n = 1 + \tfrac{1}{2} + ... + \tfrac{1}{n} \leq \log(n) + 1

    Thus \tfrac{n}{\phi(n)}<\zeta(2)\cdot \left(\log(n) + 1\right) < \left(\log(3)\right)^{k-1} \cdot \log( n) \leq \left( \log( n) \right)^k if we pick k large enough (since \log( 3) > 1 )

    Then we'd have \tfrac{n}{\phi(n)} < \left( \log( n) \right)^k = n^{k\cdot \left(\tfrac{\log\log n}{\log n}\right)} for n > 2
    You're correct, I should've said  n>2 as  \log\log2<0 .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: June 3rd 2010, 05:38 PM
  2. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 09:33 AM
  3. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 06:11 PM
  4. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2009, 07:16 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