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

Posted in Uncategorized

«
»

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.

    By: misha on April 15, 2010
    at 4:15 am

  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?

    By: Frank Morgan on April 19, 2010
    at 12:13 pm


Categories

Follow

Get every new post delivered to your Inbox.

Join 61 other followers

%d bloggers like this: