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 s ^{2}* 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

*s*be the largest square dividing

^{2}*n*and set

*r*=

*n / s*.

^{2}Next we over-estimate how many *r s ^{2}* 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 2* ^{m}*.)

How many squares are there less than *N*? No more than √*N* because if s > √*N *then *s ^{2}* >

*N*.

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*

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**:

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.

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.

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

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!

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.

“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”?)

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

Yes.

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

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?

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

Upon further thought, the inequality

2^π(N) √N ≥ N

arises from the fact that each integer == N.

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

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.

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

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