Results 1 to 3 of 3

Math Help - Euler's Totient Function and the Amount of Primes

  1. #1
    Junior Member
    Joined
    Apr 2010
    Posts
    50

    Euler's Totient Function and the Amount of Primes

    I am trying to understand a proof that shows that

    \frac{\pi(x)}{x}\leq\frac{\phi(k)}{k}+\frac{2k}{x}

    for any positive integer k and where \phi(k) is Euler's totient function.

    The proof comes to the point where it says among the integers

    k+1,k+2,\dots,2k

    there are at most \phi(k) primes. The reasoning is that "since any integer not relatively prime to k has a prime factor in common with k that is less than or equal to k."

    I understand that the reasoning is true, but I don't see how it explains that there are at most \phi(k) primes.

    Any help would be greatly appreciated.
    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2010
    Posts
    4

    Re: Euler's Totient Function and the Amount of Primes

    If k+i is a prime then we must have (i,k)=1 and there are just \phi(k) such i, so there are at most this many primes in the given sequence.

    May I ask where you are reading this proof - it looks very interesting.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2010
    Posts
    50

    Re: Euler's Totient Function and the Amount of Primes

    Quote Originally Posted by apatch View Post
    If k+i is a prime then we must have (i,k)=1 and there are just \phi(k) such i, so there are at most this many primes in the given sequence.

    May I ask where you are reading this proof - it looks very interesting.
    Thanks
    Thank you!

    That clarified everything. I am reading this proof from the book Number Theory by George E. Andrews. Here's a link to the preview of the book which contains the entire proof:

    Number theory - Google Books

    It's in Chapter 8 Section 1 page 101. The proof is actually quite interesting and there are a good amount of interesting proofs in this book.

    Thanks again.
    Last edited by Anthonny; July 16th 2011 at 06:59 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 09:33 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