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

Question

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?

Answer 1

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.

Answer 2

Presumably you know something like this:

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.