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