If k+i is a prime then we must have (i,k)=1 and there are just 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
I am trying to understand a proof that shows that
for any positive integer k and where is Euler's totient function.
The proof comes to the point where it says among the integers
there are at most 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 primes.
Any help would be greatly appreciated.
Thank you.
If k+i is a prime then we must have (i,k)=1 and there are just 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.