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²ⁿ

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+...+2N+1 < 2^2N+1.

Suppose now that n> 4 and

e^en-1 < x ≤ e^en.

Then, e^n-1 > 2ⁿ and e^en-1 > 2²ⁿ, so that

π(x) ≥ π(e^en-1) ≥ π(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

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

• Infinitude of Primes
  1. Infinitude of Primes - A Topological Proof
  2. Infinitude of Primes - A Topological Proof without Topology
  3. Infinitude of Primes Via *-Sets
  4. Infinitude of Primes Via Coprime Pairs
  5. Infinitude of Primes Via Fermat Numbers
  6. Infinitude of Primes Via Harmonic Series
  7. Infinitude of Primes Via Lower Bounds
  8. New Proof of Euclid's Theorem

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

Copyright © 1996-2012 Alexander Bogomolny