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 = p_n is the n-th prime, then for the (n+1)-st prime p_n+1 this leads to

p_n+1 < (p_n)ⁿ + 1,

for n > 1.

Lemma

p_n < 2^2ⁿ

Proof

The proof is by induction. Suppose the claim holds for 1 ≤ n < N. Then, following Euclid,

p_n+1 < p₁p₂·...·p_N + 1 < 2^{2+4+...+2^N}+1 < 2^{2^N+1}.

Suppose now that n> 4 and

e^{e^n-1} < x ≤ e^eⁿ.

Then, e^n-1 > 2ⁿ and e^{e^n-1} > 2^2ⁿ, so that

π(x) ≥ π(e^{e^n-1}) ≥ π(2^2ⁿ) ≥ 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 p_k, for a fixed k. We found that

N(x) ≤ 2^k√x.

Take now k = π(x), so that p_k+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

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

Infinitude of Primes

71930102

Infinitude of Primes Via Lower Bounds

Lemma

Proof

Reference

Infinitude of Primes
Via Lower Bounds