An elegant proof from Erdős

Here’s an elegant proof from Paul Erdős that there are infinitely many primes. It also does more, giving a lower bound on π(N), the number of primes less than N.

First, note that every integer n can be written as a product n = r s2 where r and s are integers and r is square-free, i.e. not divisible by the square of any integer. To see this, let s2 be the largest square dividing n and set r = n / s2.

Next we over-estimate how many r s2 factorizations there are less than or equal to N.

How many square-free numbers are there less than or equal to N? Every such number corresponds to a product of distinct primes each less than or equal to N. There are π(N) such primes, and so there are at most 2π(N) square-free numbers less than or equal to N. (The number of subsets of a set with m elements is 2m.)

How many squares are there less than N? No more than √N because if s > √N then s2 > N.

So if we factor every number ≤ N into the form r s2 there are at most 2π(N) possibilities for r and at most √N possibilities for s. This means

2π(N)NN

Now divide both sides of this inequality by √N and take logarithms. This shows that

π(N) ≥ log(N) / log 4

The right side is unbounded as N increases, so the left side must be unbounded too, i.e. there are infinitely many primes.

Euclid had a simpler proof that there are infinitely many primes. But unlike Euclid, Erdős gives a lower bound on π(N).

Source: Not Always Buried Deep

Related posts:

Six degrees of Paul Erdős
Five interesting things about Mersenne primes

Tagged with:
Posted in Math
15 comments on “An elegant proof from Erdős
  1. Jm says:

    There is often a lot less square-free numbers ≤N than 2^π(N). I would emphasize on the fact that the difference between pi(N) and log(N)/2 comes from this over-estimation. (Whereas the √N over-estimation of the number of squares ≤N is pretty accurate.)

    Very nice proof, though.

  2. Jitse Niesen says:

    It’s a very nice proof. I’m just wondering about a detail. I think there are *at most* 2^pi(N) square-free numbers less than or equal to N, because if you multiply primes less than N you do not necessarily get a number less than N. Of course this does not matter for the proof.

  3. _winnie says:

    There are π(N) such primes, and so there are 2π(N) square-free numbers less than or equal to N

    Why?

    If primes are less than N, it doesn’t mean that their product is less than N
    There are primes 2,3,5 below 6, but 3*5 is not less than 6.
    There are only five (1,2,3,5,6) squre-free numbers below six, not 2^3 = 8.

    Thanks for great blog records!

  4. John says:

    Thanks for the comments. Yes, I should have said “at most” regarding the number of square-free numbers <= N. I updated the post with that correction.

  5. Card Colm says:

    “Next we over-estimate how many r s2 factorizations there are less than N.”

    is it “less than or equal to N”? (i.e., “up to N”?)

  6. Michael Lugo says:

    I’m wondering if this bound can be improved by, say, counting cube-free numbers instead of square-free numbers.

  7. John says:

    Yes.

  8. Using the square-free numbers was yet employed by Hardy and Wright who actually proved that the series of the reciprocals of primes is divergent, see

    Infinitude of primes via harmonic series

  9. Felix Horns says:

    You lost me at the line:

    “So if we factor every number ≤ N into the form r s^2 there are at most 2π(N) possibilities for r and at most √N possibilities for s. This means

    2π(N) √N ≥ N”

    Could you explain this bit in more detail?

  10. J.A. Paulos says:

    Totally equivalent, of course, but I prefer [log N (base 2)/2] to [log N/log 4] for the bound.

  11. Felix Horns says:

    Upon further thought, the inequality
    2^π(N) √N ≥ N
    arises from the fact that each integer == N.

  12. Felix Horns says:

    Upon further thought, the inequality
    2^π(N) √N ≥ N
    arises from the fact that each integer ≤ N may be written as one of the products r * s^2, when we allow r to be any square-free integer with distinct prime factors each ≤ N, and s to range from 1 to √N. But among these products there may also be integers greater than N. Thus, the set of products includes at least the first N integers, and so 2^π(N) √N ≥ N.

    (HTML caused formatting problems in the last post, sorry.)

  13. beppe says:

    The Euclid argument proves that p_k is not greater than 2*3*…*p_{k-1}+1.
    Working on this furmula you prove that p_k leq 2^{2^{k-1}}, or, which is the same, that pi(N) geq log_2(log_2 N). Thus, also Euclid gives a concrete lower bound, but weaker.

  14. Andrew says:

    Michael, counting cube-free numbers resulted in a worse bound by my calculation.

  15. B-Con says:

    > How many squares are there less than N? No more than √N because if s > √N then s<sup2 > N.

    This confused me for a bit until I realized that s was being reused as an integer and not as the original largest square in N. The original definition of s doesn’t have any need to be invoked for that line.