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. An equivalent 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). His conjecture was completely proved by Pafnuty Lvovich Chebyshev (1821-1894) in 1850 and so the postulate is also called Chebyshev's theorem. Chebyshev in his proof used Chebyshev's inequality. Bertrand himself verified his statement for all numbers in the interval [2, 3 × 106].

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 px 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 is asking whether for every n>1, there is a prime p, such that n2 < p < (n+1)2.