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) √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:
Six degrees of Paul Erdős
Five interesting things about Mersenne primes
{ 14 comments… read them below or add one }
Jm 10.26.11 at 04:35
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.
Jitse Niesen 10.26.11 at 04:48
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.
_winnie 10.26.11 at 04:55
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!
John 10.26.11 at 05:53
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.
Card Colm 10.26.11 at 07:58
“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”?)
Michael Lugo 10.26.11 at 09:13
I’m wondering if this bound can be improved by, say, counting cube-free numbers instead of square-free numbers.
John 10.26.11 at 09:29
Yes.
Alexander Bogomolny 10.26.11 at 11:40
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
Felix Horns 10.26.11 at 12:50
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?
J.A. Paulos 10.26.11 at 17:01
Totally equivalent, of course, but I prefer [log N (base 2)/2] to [log N/log 4] for the bound.
Felix Horns 10.26.11 at 23:26
Upon further thought, the inequality
2^π(N) √N ≥ N
arises from the fact that each integer == N.
Felix Horns 10.26.11 at 23:36
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.)
beppe 10.27.11 at 07:47
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.
Andrew 11.02.11 at 09:07
Michael, counting cube-free numbers resulted in a worse bound by my calculation.