Counting arguments for infinitely many primes

Question

I'm looking at some fun proofs of infinitely many primes. I'm trying to understand Thue's counting proof, which I'll summarize here:

1. Assume finite primes.
2. Look at integers from $1$ to $2^n$. The cardinality of that set is $2^n$.
3. Every integer in that set can be written as $$2^{n_1}3^{n_2}5^{n_3}\cdots p^{n_k}_k$$ where the values of $n_i$ range from $0$ to $n$.
4. The cardinality of this set is $(n+1)^k$.
5. Now we have $2^n \le (n+1)^k$, which is false.

I think that the idea is to show that two different ways of counting the same thing result in different cardinalities, which can't be true. Where I'm getting lost is in the construction of the second set. I guess I don't understand why this is a fair comparison. It seems obvious to me that for certain choices of values for $n_i$, we will end up able to represent very large integers, outside the range of $2^n$. I suppose this is the origin of the inequality in (5)? But how does that connect to proving there are infinitely many primes?

Answer 1

Please don't say "infinite primes". It's "infinitely many primes".

The point is that every positive integer can be represented uniquely as a product of prime powers: $x = \prod_{i=1}^k p_i^{e_i}$ where $e_i$ are nonnegative integers. If $x \le 2^n$ then all $e_i \le n$, because $p^e > 2^n$ if $p \ge 2$ and $e > n$.

Now the proof is by contradiction. Suppose there are only finitely many, say $K$, primes $p_1, \ldots, p_K$. There are only $(n+1)^K$ integers of the form $\prod_{i=1}^K p_i^{e_i}$ where all $e_i \in \{0,1,\ldots, n\}$, and that must include all $2^n$ integers from $1$ to $2^n$. It may also include some integers $> 2^n$, but that doesn't matter. Since $2^n >(n+1)^K$ for sufficiently large $n$, we have a contradiction: there are too many integers from $1$ to $2^n$ to represent in this way.

Answer 2

The point is you do end up with integers outside the range.

Let $A=\{1,2,3,4,.......,2^n\}$.

Let $B= \{\prod p_i^{n_i}| n_i \le n\}$.

Claim $A \subsetneq B$:

Pf: well if $w \in A$ and $p$ is a prime factor and let $p^{n_i}|w$ then $n_i \le n$ because $w \le 2^{n}$ so $p^{n_i} \le 2^n$ so $n_i \le n$.

So $w \in B$. (And it's obvious $A \ne B$. $3^n \not \in A$ for starters...)

....

So $|A| < |B|$.

In the real world this is fine. As there are an infinite number of primes we have $|A| =2^n < |B| =\infty$.

But suppose

Let $p_1, p_2, .....,p_k$ be all the primes in existence. ($k$ is a fixed finite number)

Then $|B| = (n+1)^k$.

So $2^n < (n+1)^k$. This must be true for all $n$. Which it isn't.