Proof of Bertrand's Postulate - Proof of Bertrand's Postulate

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 < 468, then p can be chosen from among the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (each being less than twice its predecessor) such that n < p < 2n. Therefore n ≥ 468.

There are no prime factors p of such that:

• 2n < p, because every factor must divide (2n)!;
• p = 2n, because 2n is not prime;
• n < p < 2n, because we assumed there is no such prime number;
• 2n / 3 < p ≤ n: by computation 1 we have, so Lemma 3 applies, and by rearranging the inequalities 2n/3 < p and n ≥ p we deduce that n/p ≥ 1 and 2n/p < 3. Combining these results, we get

Therefore, every prime factor p satisfies p ≤ 2n/3.

When the number has at most one factor of p. By Lemma 2, for any prime p we have pR(p,n) ≤ 2n, so the product of the pR(p,n) over the primes less than or equal to is at most . Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:

Taking logarithms yields to

By concavity of the right-hand side as a function of n, the last inequality is necessarily verified on an interval. Since it holds true for n=467 and it does not for n=468, we obtain

But these cases have already been settled, and we conclude that no counterexample to the postulate is possible.