# Given $n$, is there a $k$ and a prime $p$ such that $10^kn < p < 10^k(n+1)$?

This is exercise 16(a) from Chapter 4, p. 102, in Tom. M. Apostol's text on analytic number theory. The chapter presents several equivalent versions of the Prime Number Theorem, the exercises there are preceded by the comment, "[i]n this group of exercises you may use the prime number theorem."

Given a positive integer $n$ there exists a positive integer $k$ and a prime $p$ such that $10^kn < p < 10^k(n+1)$.

I know that every interval contains a rational number of the form $\frac{p}{q}$, where both $p$ and $q$ are primes. So by using this property, I did try to solve exercise. But I cannot.

How should I proceed?

• One way of doing this is using Bertrand's Postulate. – Sandeep Silwal Aug 15 '16 at 16:42
• It would help to know what chapter of the book this question comes from (the topic, not just the number) so we can figure out what tools Apostol thinks you need. – Thomas Andrews Aug 15 '16 at 16:45
• In my (dusty) copy of Apostol, Exercises 12 through 16 on page 102 are preceded by the comment, "In this group of exercises you may use the prime number theorem." – Barry Cipra Aug 15 '16 at 17:21
• I specifically said, "the topic, not just the chapter number." Sigh, you are restricting the people who can help you to the people who have the book. – Thomas Andrews Aug 15 '16 at 17:52
• @ThomasAndrews: the book in Ch. 4 presents several equivalent versions of the PNT including $\pi(x) \sim x/\log x.$ – daniel Aug 15 '16 at 18:02

A similar approach to quid's answer. Since $$\pi\left(x\right)=\frac{x}{\log\left(x\right)}+o\left(\frac{x}{\log\left(x\right)}\right)$$ if we fix $a>b>0$ we have that $$\pi\left(ax\right)-\pi\left(bx\right)=\frac{ax}{\log\left(ax\right)}-\frac{bx}{\log\left(bx\right)}+o\left(\frac{x}{\log\left(x\right)}\right)$$ but note that $$\frac{1}{\log\left(Nx\right)}=\frac{1}{\log\left(x\right)+\log\left(N\right)}=\frac{1}{\log\left(x\right)}+o\left(1\right)$$ so $$\pi\left(ax\right)-\pi\left(bx\right)=\frac{ax}{\log\left(x\right)}-\frac{bx}{\log\left(x\right)}+o\left(\frac{x}{\log\left(x\right)}\right)\tag{1}$$ hence if $x$ is sufficiently large, $x>X$ say, we have that the RHS of $(1)$ is positive. Now take $a=n+1$ and $b=n$. So exists some $k$ such that $10^{k}>X$ hence $$\pi\left(10^{k}\left(n+1\right)\right)-\pi\left(10^{k}n\right)>0$$ and so the claim.
For every $\epsilon > 0$ there is an $x_{\epsilon}$ such that for $x \ge x_{\epsilon}$ there is a prime between $x$ and $(1 + \epsilon)x$
From this you get the claim with $\epsilon=1/n$ and $k$ sufficiently large such that $n10^k \ge x_{\epsilon}$.
The above is actually weaker than PNT. If you can use the PNT, and it seems you can, than you can derive the statement I mention by noticing that $\pi ((1+ \epsilon)x)\sim \frac{(1+ \epsilon)x}{\log ((1+ \epsilon)x)} \sim \frac{(1+ \epsilon)x}{\log (x)}$, whence $\pi((1+\epsilon)x) - \pi(x) \sim \frac{\epsilon x}{ \log x}$. Thus this difference is eventually always greater than $0$.
Or, you do something similar to the last paragraph with your two numbers directly, that is investigate $\pi(10^k(n+1)) - \pi(10^kn)$ using PNT as done above.