# 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 = 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})^{n} + 1,

for n > 1.

### Lemma

p_{n} < 2^{2n}

### Proof

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

p_{n+1} < p_{1}p_{2}·...·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^{n} and e^{en-1} > 2^{2n}, so that

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

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

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

Copyright © 1996-2018 Alexander Bogomolny