Proof
(related to Theorem: Infinite Set of Prime Numbers)
- Assume, there are only finitely many prime numbers \(p_1,p_2,p_3,\ldots,p_r\) with \(p_i\le n\) for some natural number \(n\). We observe that
- according to the fundamental theorem of arithmetic any \(m < n\) can be written as a product of powers of the \(p_i\) and
- 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\).
- According to the fundamental counting principle, there are at most \(2^r\) possibilities of choosing such square-free factors.
- On the other hand, from the definition of square roots, it follows that \(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\) is unbounded, so must the number \(r\) of primes smaller or equal \(n\) be. This completes the proof.
∎
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
Footnotes
