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.