Sieve of eratosthenes infinite primes

Solution 1:

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.