Posted by: Alexandre Borovik | April 14, 2010

## Some Mathematics in O()-notation

There are infinitely many prime numbers.

Proof: Assume that there are only $k$ prime numbers. Then the  number of all ways to multiply  $m$ of them (perhaps with repetitions)  is a polynomial in $m$ of degree $k$ and is therefore $O(m^k)$. On the other hand, all natural numbers up to $2^m$ can be written as a product of at most $m$ primes. Therefore $2^m \le O(m^k$ — a contradiction.

## Responses

1. Reminds me of the proof using the Euler product for the zeta function. It has a pole at 0, which can not be true if there are only finite number of primes.

2. This proof occurred to me and I posted it on April 3 at http://blogs.williams.edu/Morgan/2010/04/03/infinitely-many-primes-by-combinatorics/ Earlier references?