22
$\begingroup$

Someone gave me the following fun proof of the fact there are infinitely many primes. I wonder if this is valid, if it should be formalized more or if there is a falsehood in this proof that has to do with "fiddling around with divergent series".

Consider the product

$\begin{align}\prod_{p\text{ prime}} \frac p{p-1} &= \prod_{p\text{ prime}} \frac 1{1-\frac1p}\\&=\prod_{p\text{ prime}}\left(\sum_{i=0}^\infty\frac1{p^i}\right)\\&=(1+\tfrac12+\tfrac14+\ldots)(1+\tfrac13+\tfrac19+\ldots)\ldots&(a)\\&=\sum_{i=1}^\infty\frac1i&(b)\\&=\infty\end{align}\\\text{So there are infinitely many primes }\blacksquare$

Especially the step $(a)$ to $(b)$ is quite nice (and can be seen by considering the unique prime factorization of each natural number). Is this however a valid step, or should we be more careful, since we're dealing with infinite, diverging series?

$\endgroup$
11
  • 8
    $\begingroup$ It takes some work to make it rigorous, but yes, this is one proof of the infinitude of primes. As you say, equality of (a) and (b) are fuzzy, but you can replace $p$ with $p^s$ for $s>1$ everywhere and get the equality on both sides. Or you can just take $s=2$ and, if you know $\sum\frac{1}{n^2}=\frac{\pi^2}{6}$ and that $\pi$ is transcendental, then you know there are infinitely many primes. $\endgroup$ Jan 5, 2016 at 21:10
  • 5
    $\begingroup$ The proof actually works somewhat different : It is assumed that the number of primes is finite. Then the given product would be finite, so the harmonic series would converge. This is not the case, hence the assumption, that only finite many primes exist, must be false. $\endgroup$
    – Peter
    Jan 5, 2016 at 21:11
  • 3
    $\begingroup$ This is the way Euler did it: en.wikipedia.org/wiki/Euclid%27s_theorem#Euler.27s_proof. $\endgroup$
    – lhf
    Jan 5, 2016 at 21:15
  • 3
    $\begingroup$ @aronp It might well be circular - either the proof of $\zeta(2)=\frac{\pi^2}{6}$ or the proof that $\pi^2$ is irrational might require infinitely many primes, for all I know. $\endgroup$ Jan 5, 2016 at 21:20
  • 2
    $\begingroup$ @ThomasAndrews - its not, seen quite a few proofs of Zeta(2) and non involved primes. Your proof is nice, get over it. $\endgroup$
    – aronp
    Jan 5, 2016 at 21:23

1 Answer 1

19
$\begingroup$

The rigorous approach, as noted in comments.

If there are only finitely many primes, pick an $n$ so that:

$$H_n=\sum_{m=1}^{n}\frac{1}m > \prod_{p}\frac{1}{1-\frac 1p}$$

You can do this because the right side is a finite product of positive real numbers, and the series $\sum_{m=1}^{\infty}\frac1m$ diverges.

Next, show that:

$$\prod_p \frac{1}{1-\frac{1}{p}} > \prod_p \sum_{k=0}^{\lfloor \log_{p}n\rfloor} \frac{1}{p^k}>\sum_{m=1}^{n}\frac{1}{m}$$

Reaching a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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