Infinitely Many Primes by Combinatorics

Here’s a proof of the infinitude of primes that occurred to me when for some reason Delta upgraded me to First Class on a flight April 2. Can anyone provide a reference?

Suppose that the set P of primes and 1 has just n+1 elements. Now every number at most 2k can be obtained by choosing k elements of P with replacement, which can be done in (k+n choose n) ways. Therefore

2k ≤ (k+n choose n) ≤ (k+n)n ,

which fails for k large.

5 Comments

  1. MB:

    Clearly you prove this by assuming a finite number of primes, and showing this leads to a contradiction like is usual, but can you explain to a novice in combinatorics how the inequalities follow? Specifically, how does your argument imply 2^k ≤ (k+n choose n) ≤ (k+n)^n ?

    A number ≤ 2^k has at most k prime factors and hence is a product of exactly k numbers from our set P. It is a standard combinatorial formula (see any Discrete Math text) that the number of ways to choose k numbers from a set with n elements (allowing repetition) is (k+n choose n) = (k+n)(k+n-1)… ≤ (k+n)^n. —FM

  2. Andrew McIntyre:

    Hi,

    You mentioned this proof to me at the HRUMC the other day, and I said that I had just heard it somewhere else recently.

    What I was thinking of was this post on Alexandre Borovik’s blog – not the same as yours, but similar. He credits it to Dmitri Fon-Der-Flaass.

    andrew

  3. Frank Morgan:

    Thanks Andrew, interesting, same proof, based on Russian post by Dmitri Fon-Der-Flaass of same date as my post. I posted a comment on Borovik’s blog.

    Frank

  4. Andrew McIntyre:

    Whoa, synchronicity!

  5. LJS:

    This seems to be more or less the argument credited to Thue at

    http://www.gbbservices.com/math/primes.html

Leave a Reply

Your email address will not be published.