Proof of Bertrand's postulate
(One statement of)
Bertrand's postulate is that for each
n ≥ 2 there is a
prime p such that
n <
p < 2
n. It was first
proven by
Pafnuty Chebyshev, but the gist of the following elementary but involved
proof by contradiction is due to
Paul Erdös. We denote the set of prime numbers with and define:
Lemma
-
Proof
(by
induction)
- and n is odd. Let n = 2m+1 with m > 0:
Each prime p with divides giving us:
By induction , so:
-
Q.E.D
Now for the proof of Bertrand's postulate.
Assume there is a counterexample: an integer n ≥ 2 such that there is no prime p with n < p < 2n.
If 2 ≤ n;; < 2048, then one of the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 and 2503 (each being less than twice its predecessor), call it p, will satisfy n < p < 2n''.
Therefore n ≥ 2048.
Since is the largest term in the
sum we have:
Define to be highest number
x, such that divides .
Since
nFactorial has factors of
p we get:
Since each term can either be 0 or 1 and all terms with are 0 we get:
For we have or .
has no prime factors p such that:
- 2n < p, because 2n is the largest factor.
- , because of a trivial expansion of the original assumption.
- , because (since ) which gives us .
Each prime factor of is therefore not larger than .
has at most one factor of every prime . As , the product of over all other primes is at most . Since is the product of over all primes p, we get:
Using our lemma :
Since we have :
Also (since ):
Taking
logarithms:
Substituting 2
2t for 2
n:
This gives us
t<6 and the contradiction:
Thus no counterexample to the postulate is possible.
Q.E.D.