Posted by: Alexandre Borovik | April 14, 2010

Some Mathematics in O()-notation

From Dmitri Fon-Der-Flaass:

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.


  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 Earlier references?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



Get every new post delivered to your Inbox.

Join 99 other followers

%d bloggers like this: