# Using Euler Phi function to show that there are infinitely many primes

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

-

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$.
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
@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