Engineering / Mathematics — The Distribution of Primes
Bertrand's Postulate
Bertrand's postulate that a prime always lies between n and 2n, its elementary proof, and its use in algorithm analysis.
Executive summary
Bertrand's postulate asserts that for every integer n greater than 1 there is a prime strictly between n and 2n. Conjectured by Bertrand and first proved by Chebyshev, it has an elementary proof by the same binomial machinery.
It guarantees that primes of any desired bit length exist, which is precisely what random prime generation needs.
Learning objectives
- State the postulate precisely.
- Outline the binomial coefficient proof.
- Apply it to justify prime generation by bit length.
01The statement
Bertrand's postulate
For every integer n > 1 there is a prime p with n < p < 2n.
The result is stronger than it may appear. Chebyshev's bounds give the number of primes up to a constant factor, but a constant factor is not enough to guarantee a prime in every dyadic interval — the constants could in principle permit a gap. Bertrand's postulate closes that.
02The proof strategy
The argument again studies C(2n,n), but now the goal is to show its prime factorisation must include a prime above n. Suppose not, and bound the coefficient using only primes below n.
Split the primes
Partition the primes dividing C(2n,n) by size: those below √(2n), those between √(2n) and 2n/3, and those between 2n/3 and n.
Bound each class
Primes below √(2n) contribute at most (2n)^{√(2n)}. Primes in the middle range contribute at most 4^{2n/3}. Primes between 2n/3 and n contribute nothing at all.
Compare with the lower bound
The product of these bounds is smaller than 4^n/(2n+1) for n sufficiently large, a contradiction.
Check small cases
The finitely many remaining n are verified directly using a short explicit list of primes.
The vanishing contribution of primes between 2n/3 and n is the surprising step. Such a prime p satisfies 3p > 2n, so exactly two multiples of p appear below 2n and one below n, and the exponent in the coefficient cancels to zero.
03Use in algorithm analysis
Prime generation
Guarantees a k-bit prime exists, so a search over k-bit candidates cannot fail for lack of a target.
Density estimate
Combined with Chebyshev, gives that a random k-bit odd number is prime with probability about 2/(k ln 2), fixing the expected number of trials.
Parameter selection
Assures that primes with prescribed size constraints can be found, which cryptographic key generation requires.
Sharper versions are known: primes exist in much shorter intervals than [n, 2n] for large n, and under the Riemann hypothesis the intervals shrink dramatically. Bertrand's postulate is the version that is both elementary and unconditional, which is why it remains the one cited.
04Frequently asked questions
Is Bertrand's postulate still a postulate?
No, it is a theorem — the name is historical. Bertrand conjectured it in 1845 after verifying it numerically, and Chebyshev proved it in 1852.
Are there primes in shorter intervals?
Yes, for large n. It is known that intervals of length about n^0.525 contain primes for sufficiently large n, and much stronger results follow from the Riemann hypothesis. None of these is elementary.
Does it help find a prime, or only show one exists?
Only existence. Locating the prime still requires testing candidates, which is what Miller-Rabin does. The postulate guarantees the search terminates.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 78-81.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.