2
$\begingroup$

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

1 Answers 1

4

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?

  • 0
    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. = )2012-11-30
  • 0
    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.2012-11-30
  • 1
    @Zxy Precisely. $\phi(m) = \#\{n \leq m: \gcd(m,n) = 1\}$2012-11-30
  • 0
    @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.2012-11-30