# Simple Application of Prime Number Theorem

I was wondering if someone could possibly help me verify the following:

For sufficiently large $n$ there is always a prime between $n- \sqrt{n}$ and $n$.

I am not sure if this is true or not. If it is true could you possibly explain me how the Prime number theorem is applied to get the answer?

-

I do not think you will have an easy time proving this result. There are a number of reasons for this. First, the Legendre conjecture states that there is at least one prime between $n^2$ and $(n+1)^2$, an interval of length that is order of $n$. As far as I know this is still unsolved. If we rescale your problem, we get that you want to show there are primes between $n^2-n$ and $n^2$ for $n$ large enough. Notice that $(n-1)^2=n^2-2n+1<n^2-n$. So if you could show your statement to be true, then you will have proven the Legendre conjecture for large enough $n$, and if you could produce a good lower bound on $n$ then a computer search will likely prove the Legendre conjecture.

The prime number theorem says $\pi(n)=O(n/\log(n))$. In fact the limit of the ratio is 1. So for all $0<C<1$, there exists a $N_c$, such that for all $n\geq N_c$,

$$c\leq \frac{\pi(n)}{n/\log(n)}$$

The interval you have is of length $\sqrt{n}$. In fact, the interval $[1,n]$ can be broken into $[1,n-\sqrt{n}]$ and $[n-\sqrt{n},n]$. In other words, you could try showing that there are at least $n-\sqrt{n}$ primes. No matter what $c$ you chose in the above, you will not attain a density this high for all large $n$.

You also might be interested in the Oppermann Conjecture which is a somewhat stronger version of your problem.

-
Now reread the question title: "Simple application ..." :) –  Hagen von Eitzen Nov 30 '12 at 23:43
You could try looking for asymptotic results of Legendre's conjecture. I'm not an expert but I don't think much is known. –  Alex R. Nov 30 '12 at 23:45
Ooopps. I guess it's not simple after all. Thank you very much! –  J Kasahara Nov 30 '12 at 23:56