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

15 thoughts on “An elegant proof from Erdős

  1. 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. 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. 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. 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. “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. 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?

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

  8. 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.)

  9. 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.

  10. > 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.

Comments are closed.