Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know Euclid's clever way of proving that there are infinitely many primes but while I was studying, I also saw a sentence on the book: "Euler-phi function can also be used to show that there are infinitely many primes." but could not figure out how. Could you please help me to understand it?

Regards

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Assume that there are only a finite number of primes say $p_1,p_2,\ldots,p_k$. Look at the product of these finite primes i.e. $$m = p_1 p_2 \cdots p_k$$ Now consider any number $n > 1$. Since there are only finite primes, one of the $p_j$'s must divide $n$. Hence, $\gcd(m,n) > 1$. Hence, $\phi(m) = 1$.

Can you now finish it off?

share|improve this answer
    
I guess it must go on like this: we know that $\phi(m) = 1$ however according to the multiplicative property of the phi function, $\phi(m) = (p_1-1)*(p_2-1)*...*(p_k-1)$ which is not clearly equal to 1. However I could not exactly understand why $\phi(m) = 1$. Maybe I should give it some time. = ) –  Amadeus Bachmann Nov 30 '12 at 2:27
    
I guess I understood why $\phi(m) = 1$. Any selection of (m,n) will not be relatively prime only (m,1) will be relatively prime hence $\phi(m) = 1$. That is brilliant. Thank you so much. –  Amadeus Bachmann Nov 30 '12 at 2:30
1  
@Zxy Precisely. $\phi(m) = \#\{n \leq m: \gcd(m,n) = 1\}$ –  user17762 Nov 30 '12 at 2:32
    
@Zyx $\rm\:m \ge 2\:\Rightarrow\:1\ne m\!-\!1\:$ are both coprime to $\rm\:m\:$ so $\rm\:\phi(m)\ge 2.\:$ This is just the $\rm\:m\!-\!1\:$ (vs. $\rm\:m\!+\!1)\:$ form of Euclid's proof. –  Bill Dubuque Nov 30 '12 at 3:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.