Infinite Number of Primes (Euklid)

Analytic Proof (Erdös 1938)

(related to "Infinite Number of Primes")

Let \(n\) be any natural number and \(p_1,p_2,p_3,\ldots,p_r\) the complete set of primes with \(p_i\le n\). We observe that

1. any \(m < n\) can be written as a product of powers of the \(p_i\) and
2. any integer (\(m\) in particular!) can be written as the product of a square and a square-free integer¹.

Using these observations, for each such \(m\) we can write
\[m=k^2\times p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_r^{e_r},\]
where \( e_i \in \left\{ 0,1 \right\} \), depending on whether a particular prime number is present or not in the square-free factor of \(m\). Consequently, there are at most \(2^r\) possibilities of choosing such square-free factors. On the other hand, it is clearly \(k^2\le n\) and \(k\le \sqrt n\).

It follows that integers smaller than \(n\) can be chosen in at most \(2^r\times\sqrt n\) ways, in other words
\[n\le 2^r\times\sqrt n,\]
resulting in
\[\sqrt n\le 2^r,\]
and
\[\frac 12\log_2 n\le r.\]
Since \(n\) ist unbounded, so must the number \(r\) of primes smaller or equal \(n\) be. This completes the proof.

¹ This is clear enough if the integer is factorized into the product of its prime factors and the repeated ones are collected together. For example, \(5096=2^3\cdot 7^2\cdot 13=(2\cdot 7)^2 \cdot (2\cdot 13)\).

Contribute to BoP:

add a new Open Problem  N

add a new Comment (Branch)  N