Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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...?

share|cite|improve this question
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
up vote 4 down vote accepted

Not a full answer, but hopefully helpful progress:

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...


$$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$.


$$\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 .

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.