Infinitude of Primes
Via Lower Bounds
A common convention is to denote the number of primes below N as π(N). The fact that there are infinitely many primes is equivalent to
In Euclid's proof we form the product of the first primes and consider an expression,
q = 2·3·5·7·...·p + 1.
If p = pn is the n-th prime, then for the (n+1)-st prime pn+1 this leads to
pn+1 < (pn)n + 1,
for n > 1.
pn < 22n
The proof is by induction. Suppose the claim holds for 1 ≤ n < N. Then, following Euclid,
pn+1 < p1p2·...·pN + 1 < 22+4+...+2N+1 < 22N+1.
Suppose now that n> 4 and
een-1 < x ≤ een.
Then, en-1 > 2n and een-1 > 22n, so that
π(x) ≥ π(een-1) ≥ π(22n) ≥ n.
Since ln(ln(x)) ≤ n, we deduce that
π(x) ≥ ln(ln(x)).
Now, this is a matter of direct verification that the same inequality is also true for
π(N) → ∞, for N → ∞.
We may actually do better. Elsewhere we defined N(x) as the number of terms not exceeding x and not divisible by any prime above pk, for a fixed k. We found that
N(x) ≤ 2k√x.
Take now k = π(x), so that pk+1 > x and
x = N(x) ≤ 2π(x)√x,
implying √x ≤ 2π(x). Thus we have
π(x) ≥ ln(x)/ln(4).
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1996, p. 12, p.17
Copyright © 1996-2018 Alexander Bogomolny