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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
8  
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. – Thomas Andrews Jan 5 at 21:10
5  
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. – Peter Jan 5 at 21:11
3  
This is the way Euler did it: en.wikipedia.org/wiki/Euclid%27s_theorem#Euler.27s_proof. – lhf Jan 5 at 21:15
3  
@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. – Thomas Andrews Jan 5 at 21:20
2  
@ThomasAndrews - its not, seen quite a few proofs of Zeta(2) and non involved primes. Your proof is nice, get over it. – aronp Jan 5 at 21:23
up vote 19 down vote accepted

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.

share|cite|improve this answer

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.