# Thread: Euler's Totient Function and the Amount of Primes

1. ## Euler's Totient Function and the Amount of Primes

I am trying to understand a proof that shows that

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

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

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

$\displaystyle k+1,k+2,\dots,2k$

there are at most $\displaystyle \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 $\displaystyle \phi(k)$ primes.

Any help would be greatly appreciated.
Thank you.

2. ## 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 $\displaystyle \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

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

Originally Posted by apatch
If k+i is a prime then we must have (i,k)=1 and there are just $\displaystyle \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: