Bertrand's postulate states that if n>3 is an integer, then there always exists at least one prime number p with n < p < 2n-2. A weaker but more elegant formulation is: for every n > 1 there is always at least one prime p such that n < p < 2n.

This statement was first conjectured in 1845 by Joseph Bertrand (1822-1900). Bertrand himself verified his statement for all numbers in the interval [2, 3 × 10⁶]. His conjecture was completely proved by Pafnuty Lvovich Chebyshev (1821-1894) in 1850 and so the postulate is also called Chebyshev's theorem. Srinivasa Aaiyangar Ramanujan (1887-1920) gave a simpler proof and Paul Erdős (1913-1996) in 1932 published a simpler proof using the function θ(x), defined as:

where p ≤ x runs over primes, and the binomial coefficients. See proof of Bertrand's postulate for the details.

Sylvester's theorem

Bertrand's postulate was proposed for applications to permutation groups. James Joseph Sylvester (1814-1897) generalized it with the statement: the product of k consecutive integers greater than k is divisible by a prime greater than k.

A similar and still unsolved conjecture asks whether for every n>1, there is a prime p, such that n² < p < (n+1)².