Take the 2-minute tour ×

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|improve this question

3 Answers 3

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|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|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|improve this answer
Possibly it is this question you have in mind: mathoverflow.net/questions/53498/nontrivial-circular-arguments –  quid Apr 27 '11 at 19:00
Yes, that's the one. –  Qiaochu Yuan Apr 27 '11 at 20:11

Your Answer


