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.

About these ads

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?


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

Categories

Follow

Get every new post delivered to your Inbox.

Join 77 other followers

%d bloggers like this: