Bertrand’s conjecture, proof of

This is a version of Erdős’s proof as it appears in Hardy and Wright.

We begin with the following lemma.


Let n be a positive integer and p be a prime. The highest power of p dividing n! is jnpj, where x is the floor of x.


Let pk divide n! with k as large as possible. Every pth term of the sequenceMathworldPlanetmath 1,,n is divisible by p, so contributes a factor to pk. There are np such factors. Every p2th term contributes an extra factor above that, providing np2 new factors. In general, the pjth terms contribute npj extra factors to pk. So the highest power of p dividing n! is jnpj. ∎

We now prove the theoremMathworldPlanetmath.

Bertrand’s conjecture.

Let n>2 be a minimal counterexample to the claim. Thus there is no prime p such that n<p<2n.

In the sequence of primes


each succeeding term is smaller than the double of its predecessor. This shows that n2503.

The binomial expansion ( of (1+1)2n has 2n+1 terms and has largest term (2nn). Hence


For a prime p define r(p,n) to be the highest power of p dividing (2nn). To compute r(p,n), we apply the lemma to (2n)! and n!. We get that


The terms of the sum are all 0 or 1 and vanish when j>log(2n)logp, so r(p,n)log(2n)logp, that is, pr(p,n)2n.

Now (2nn)=ppr(p,n). By the inequalityMathworldPlanetmath just proved, primes larger than 2n do not contribute to this productPlanetmathPlanetmath, and by assumptionPlanetmathPlanetmath there are no primes between n and 2n. So

(2nn)=1pnp primepr(p,n).

For n>p>2n3, 32>np>1 and so for p>2n3>2n we can apply the previous formulaMathworldPlanetmathPlanetmath for r(p,n) and find that it is zero. So for all n>4, the contribution of the primes larger than 2n3 is zero.

If p>2n, all the terms for higher powers of p vanish and r(p,n)=2np-2np. Since r(p,n) is at most 1, an upper boundMathworldPlanetmath for the contribution for the primes between 2n and 2n3 is the product of all primes smaller than 2n3. This product is exp(ϑ(2n3)), where ϑ(n) is the Chebyshev functionMathworldPlanetmath

ϑ(n)=pnp primelogp.

There are at most 2n primes smaller than 2n and by the inequality pr(p,n)2n their product is less than (2n)2n. Combining this information, we get the inequality


Taking logarithms and applying the upper bound of nlog4 for ϑ(n) (, we obtain the inequality n3log4(2n+2)log(2n), which is false for sufficiently large n, say n=211. This shows that n<211.

Since the conditions n2503 and n<211 are incompatible, there are no counterexamplesMathworldPlanetmath to the claim. ∎


  • 1 G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938.
Title Bertrand’s conjecture, proof of
Canonical name BertrandsConjectureProofOf
Date of creation 2013-03-22 13:18:55
Last modified on 2013-03-22 13:18:55
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 15
Author CWoo (3771)
Entry type Proof
Classification msc 11N05