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 π(N) →  when N → .

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.

Lemma

pn < 22n

Proof

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 x = 2 and n = 3. Therefore, it holds for n ≥ 2. In any event, it implies that

π(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) ≤ 2kx.

Take now k = π(x), so that pk+1 > x and N(x) = x. Then,

x = N(x) ≤ 2π(x)x,

implying x ≤ 2π(x). Thus we have

π(x) ≥ ln(x)/ln(4).

Reference

  1. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1996, p. 12, p.17

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

71491767