# At least one prime between $\sqrt{n}$ and $n$?

Prove that for all $n>2$ there exists at least one prime $p$ such that $\sqrt{n}<p<n$ using elementary methods.

My try: If not, $\sum_{p<\sqrt{n}} (\lfloor n/p \rfloor-\lfloor \sqrt{n}/p \rfloor) \geq n-\sqrt{n}$ then...?

-
Even stronger: Chebyshev's theorem: There is a prime between $n$ and $2n$. There is a completely elementary proof by P. Erdös, essentially analyzing prime factors of ${2n\choose n}$. – Your Ad Here Feb 9 '14 at 0:27
So I know about Chebyshev... but not the proof. Is the proof complicated? Is there a simple one for the problem I stated? – nayrb Feb 9 '14 at 0:28
But you must go read that proof by Erdös, it's one of the coolest ideas ever! – Your Ad Here Feb 9 '14 at 0:29
@TooOldForMath I think it's Bertrand postulated. Tchebychev gave an analytic proof of the postulate. – user119228 Feb 9 '14 at 0:52
@nayrb I suggest you look at the proof here and simplify it to give the weaker result, i.e. look at ${n\choose \lfloor\sqrt{n}\rfloor}$ instead. Several of the estimates should then be easier. – Your Ad Here Feb 9 '14 at 0:56

Look at $M_p := \binom{p^2}{p~p~\ldots~p} = \frac{p^2!}{p!^p}$ where $p$ is a prime number, let $v_q(x)$ the q-adic valuation of $M_p$ : $$v_q(M_p) = \sum_{k \geq 1} \lfloor\frac{p^2}{q^k}\rfloor - p\lfloor \frac{p}{q^k}\rfloor \leq (p-1)\lfloor \log_q(p^2) \rfloor$$ Thus, $$q^{v_q(M_p)} \leq p^{2(p-1)}$$ In particular, if the interval $\{p+1,\ldots,p^2\}$ does not include any prime number, then $$M_p \leq p^{2(p-1)\pi(p)}$$ where $\pi(p)$ is the number of prime numbers is the interval $\{p+1,\ldots,p^2\}$.

Moreover we know that $\ln(n!) \sim n \ln(n)$.Thus, $$\ln(M_p) \sim p^2 \ln(p)$$ Because $2(p-1)\pi(p) \ln(p)$ is very small compared to $p^2 \ln(p)$

We know that your inequality will be true from a certain rank. Finding explicit bounds for a similar result to $\ ln (n!) \sim n \ ln (n)$, we will win...

Edit:

$$n \ln(n) \geq \ln(n!) \geq \frac{2n}{3} \ln(\frac{n}{3})$$

Then, $$\ln(M_p) \geq \frac{9p^2}{10} \ln(\frac{p^2}{10}) - p^2 \ln(p) = \frac{p^2}{10} (8\ln(p) - 9 \ln(10))$$ Therefore, $\ln(M_p) \geq \frac{p^2}{2} \ln(p)$ since $ln(p) \geq 10^3$.

Yet, $$\pi(n) \leq 4 + \frac{1}{2} \frac{2}{3} \frac{4}{5} \frac{6}{7} (n+1) = 4 + \frac{8(n+1)}{35}$$ for all integer n$\geq 0$.

Thus,

$$\frac{p^2}{2} \ln(p) \leq \ln(M_p) \leq \frac{2}{35}(p-1)(8p+140)\ln(p)$$

In the same way, $$35 p^2 \leq 4(p-1)(8p+140)$$ ie $$0 \geq 35p^2-4(p-1)(8p+140) =3p^2-528p+560 > 3((p-88)^2-88^2)$$

Therefore $p < 176$

Thus , it is known that the interval $\{p+1,\ldots,p^2-1\}$ has a prime number when $p \geq 10^3$

but $3, 7, 47, 1009$ are prime numbers.

So the interval $\{p +1, \ldots , p ^ 2-1 \}$ has a prime number when $p \geq 2$ . This completes your exercise .

-

By way of a bump, I'm answering my question to give two facts and hope someone can give a good answer from this or at least convince me it will be too hard to do.

The first is that if $n=pq$ where $p$ and $q$ are primes then the claim is true. This is because if both $p,q<\sqrt{n}$ we get $n<n$.

The second is that the statement is equivalent to proving that if $p$ is a prime, the next prime $q$ is $q<p^2$. That is, the statement holds if it holds for $n=p^2$, $p$ prime. One does an induction argument, assuming there is a prime $p$ with $\sqrt{n}<p<n$, and then consider the interval $\sqrt{n+1}$ to $n+1$. If it doesn't contain a prime, it must be because $\sqrt{n}<p \leq \sqrt{n+1}$. Squaring gives the conclusion $n+1=p^2$, reducing the problem.

-