4
$\begingroup$

I don't understand why the sieve of eratosthenes doesn't prove an infinite number of primes. For example the number 2 eliminates 1/2 of an infinite number of numbers. The next prime, 3, eliminates 1/3 of the remainder, not 1/3 of all the numbers and so on. 5 would eliminate 1/5 of the remaining numbers. Why doesn't that prove an infinite number of primes? Thanks

$\endgroup$
  • 1
    $\begingroup$ Welcome to this site, the sieve of Eratosthenes doesn't prove the existence of an infinite number of primes itself, it is just a way "an algorithm" to find all primes which are less than N. But if you want to prove that there are infinitely many primes using this sieve you have to prove that after every k iterations there is always a number which is not eliminated (this is easy you can just take $N=p_1\cdots p_k+1$ but it's not included in Eratosthenes's sieve). $\endgroup$ – Elaqqad Feb 17 '15 at 14:29
4
$\begingroup$

Your argument is absolutely correct. Suppose the primes are labeled $p_1,p_2,\dots.$ The key observation is that different primes are coprime, so the density of numbers that divide both $p_1$ and $p_2$ is $\frac1{p_1p_2}$ and similarly for other subsets of the primes (this can also be seen as a corollary of the Chinese remainder theorem). Let $A_i$ be the set of all natural numbers which do not divide any of $p_1,p_2,\dots,p_i$. Then \begin{align}d(A_0)&=1,\\ d(A_1)&=d(A_0)\left(1-\frac1{p_1}\right)=\frac{p_1-1}{p_1},\\ d(A_2)&=d(A_1)\left(1-\frac1{p_2}\right)=\frac{p_1-1}{p_1}\frac{p_2-1}{p_2},\\ &\dots\\ d(A_n)&=\prod_{i=1}^n\frac{p_i-1}{p_i},\\ &\dots \end{align}

In particular, $d(A_n)$ is a product of positive numbers, which is positive, so that $A_n\ne\emptyset$ for every $n$. If there were finitely many primes, we would have $A_n$ empty after we hit all the primes, so this is a valid proof of the infinitude of primes.

$\endgroup$
  • $\begingroup$ Sorry, but what does $d(n)$ mean? $\endgroup$ – user3141592 May 28 '17 at 22:51
  • 1
    $\begingroup$ @user3141592 For a subset of the natural numbers $A\subseteq\Bbb N$, $d(A)$ is the density of the set, which can be thought of as the probability that a randomly chosen integer is in the set $A$. (It's not always well-defined, but it is whenever $A$ is periodic, as in this case.) $\endgroup$ – Mario Carneiro May 29 '17 at 6:14
  • $\begingroup$ But then, following your argument and by Mertens' Theorem we would get that as $n \to \infty$, $d(A_n)=\frac{1}{e^\gamma \log(n)}$, which differs from the correct solution given by the PNT by the $e^{-\gamma}$ factor, isn't it? $\endgroup$ – user3141592 May 29 '17 at 9:31

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.