MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a result in the spirit of Bertrand-Chebyshev which talks about the existence of prime powers between n and 2n (or 3n or something like that) for n large?

share|cite|improve this question
up vote 7 down vote accepted

It follows from the prime number theorem that for fixed $k$, provided $n$ is sufficiently large, there is a prime $p$ such that $p^k$ is between $n$ and $2n$. Does this answer your question?

share|cite|improve this answer
Thank you very much for your quick answer. Yes, it answers the question, and it goes to show the power of the PNT. – Chebolu Apr 27 '11 at 16:01
I wonder if there is an elementary proof of this without using PNT, like Erdős' proof of Bertrand's Postulate? – Tony Huynh Apr 27 '11 at 17:24

Actually there is a power of 2. It goes to show the power of binary arithmetic ... : write 2n in binary and write zeroes after the initial one.

share|cite|improve this answer
In other words, if $2^{k - 1}$ is the largest power of 2 less than n, then $n \leq 2^k < 2n$? – Ryan Reich Apr 27 '11 at 18:14
Yes, you said it. – Charles Matthews Apr 27 '11 at 18:43

For fixed $k$, the existence of a prime power $p^k$ between $n$ and $2n$ is (asymptotically) equivalent to the existence of a prime $p$ between $m$ and $\sqrt[k]{2} m$ where $m = \sqrt[k]{n}$. Bachraoui gives an elementary proof here that there exists a prime between $m$ and $\frac{3}{2} m$ for sufficiently large $m$.

I remember reading on MO that it is known that similar elementary proofs exist for showing the existence of primes between $m$ and $(1 + \epsilon) m$ for any $\epsilon > 0$ and, furthermore, that the existence of these proofs itself depends on the PNT. However, I can't track down where I read this.

share|cite|improve this answer
Possibly it is this question you have in mind: – user9072 Apr 27 '11 at 19:00
Yes, that's the one. – Qiaochu Yuan Apr 27 '11 at 20:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.