Consider the following statement:

For any integer $n>1$ there is a prime number strictly between $n$ and $n^2$.

This problem was given as an (extra) qualification problem for certain workshops (which I unfortunately couldn't attend). There was a requirement to not use Bertrand's postulate (with which the problem is nearly trivial), and I was told that there does exist a moderately short proof of this statement not using Bertrand. This is my question:

How can one prove the above statement without Bertrand postulate or any strong theorems?

Although I can only accept one answer, I would love to see any argument you can come up with.

I would also want to exclude arguments using a proof of Bertrand's postulate, unless it can be significantly simplified to prove weaker statement.

Thank you in advance.

  • 2
    $\begingroup$ Is it this what you're looking for? mathoverflow.net/questions/52060/… $\endgroup$ – Riley Dec 30 '15 at 18:09
  • 1
    $\begingroup$ @Riley The proof given in that link does prove what I want. I am going to leave my question here nevertheless in hopes of seeing other approaches. Feel free to post this proof as an answer here as well. $\endgroup$ – Wojowu Dec 30 '15 at 18:16
  • $\begingroup$ What a maddeningly simple problem! I thought about maybe assuming that there are no primes at all between $n$ and $n^2$ (though $n$ itself may be prime) and then drawing a contradiction. But then what contradiction? $\endgroup$ – Robert Soupe Dec 31 '15 at 3:24
  • $\begingroup$ Do Mertens' theorems count as "strong theorems"? $\endgroup$ – Daniel Fischer Jan 3 '16 at 13:11
  • 1
    $\begingroup$ Can't say I'm surprised. $\endgroup$ – Daniel Fischer Jan 3 '16 at 13:14

I have stumbled upon this paper due to Erdős, which in the course of proving something far more general proves this result (see a remark at the end of this page). I am replicating that proof here, with minor modifications by myself.

Suppose $n>8$ and that there are no primes between $n,n^2$. Since clearly (obvious induction works) $\pi(n)\leq\frac{1}{2}n$, by assumption we have $\pi(n^2)=\pi(n)\leq\frac{1}{2}n$. Now consider number $\binom{n^2}{n}$. All of its prime factors are less than $n^2$, and so less than $n$. We have the following inequality:


At the same time, consider $p$ prime and let $p^a$ be the greatest power of $p$ less than or equal to $n^2$. Since $\binom{n^2}{n}=\frac{(n^2)!}{(n^2-n)!n!}$, By Legendre's formula, exponent of the greatest power of $p$ dividing this binomial coefficient is equal to

$$\left(\lfloor\frac{n^2}{p}\rfloor-\lfloor\frac{n^2-n}{p}\rfloor-\lfloor\frac{n}{p}\rfloor\right)+\left(\lfloor\frac{n^2}{p^2}\rfloor-\lfloor\frac{n^2-n}{p^2}\rfloor-\lfloor\frac{n}{p^2}\rfloor\right)+\dots+\left(\lfloor\frac{n^2}{p^a}\rfloor-\lfloor\frac{n^2-n}{p^a}\rfloor-\lfloor\frac{n}{p^a}\rfloor\right)\leq 1+1+\dots+1=a$$

(first equality is true, because all further terms in the sum are zero. First inequality is true because for any $a,b\in\Bbb R$ $\lfloor a+b\rfloor-\lfloor a\rfloor-\lfloor b\rfloor\in\{0,1\}$)

Since $\binom{n^2}{n}$ is a product of at most $\pi(n)$ prime powers, all at most $p^a\leq n^2$ (by above), we must have

$$\binom{n^2}{n}\leq (n^2)^{\pi(n)}\leq (n^2)^{\frac{1}{2}n}=n^n$$

We have proved two contradictory inequalities, so this ends the proof by contradiction.


After a little bit of searching on the net, it seems that this result isn't as easy to prove (without Bertrand that is) as one would hope. However, here: https://mathoverflow.net/a/52085, you can find the proof of the result you're looking for. Basically, the author shortens Bertrand's Postulate's proof so that it only proves your desired result.

  • 1
    $\begingroup$ It seems to me that the author of the answer actually proves the result for all $n>1$, not only primes. $\endgroup$ – Wojowu Dec 30 '15 at 21:19
  • $\begingroup$ @Wojowu, You're absolutely right! $\endgroup$ – Riley Dec 30 '15 at 21:35

I've come up with a simple proof based on the prime-counting function $\pi(x)$, which I'm pretty sure doesn't depend on Bertrand's Postulate.

First, I will prove a lemma that for every prime $n$, there is another prime $p$ with $n < p < n^2$. I will use this result later to show the general result (i.e. for composite $p$ as well).

Based on some inequalities of $\pi(x)$ and the value of a related constant we have $$\frac{n}{\log n} < \pi(n) < C\frac{n}{\log n}\text{, where }C=\pi(30)\frac{\log 113}{113} \approx 1.255$$ for all $n \geq 17$. We want to prove that for all prime $n$ we have $$\pi(n^2) > \pi(n)$$ or $$\pi(n^2) - \pi(n) > 0,$$ so we look at the upper bound of $\pi(n)$ and the lower bound of $\pi(n^2)$ to find a minimum difference.

We have $$\begin{align} \pi(n^2) - \pi(n) &> \frac{n^2}{\log n^2} - C\frac{n}{\log n} \\ &= \left(\frac{n}{2} - C\right)\frac{n}{\log n} \end{align} $$ so the conclusion is satisfied whenever $$\left(\frac{n}{2} - C\right)\frac{n}{\log n} > 0.$$ Since for all prime $n$ we have $$\frac{n}{\log n} > 0,$$ we find that $\pi(n^2) - \pi(n) > 0$ whenever $\frac{n}{2} - C > 0$, which gives us $$n > 2C \approx 2.51$$ so $$n \geq 3$$ which is true for every prime $n \geq 17$.

For lesser primes we can prove things manually: $$2 < 3 < 2^2$$ $$3 < 5 < 3^2$$ $$5 < 7 < 5^2$$ $$7 < 11 < 7^2$$ $$11 < 13 < 11^2$$ $$13 < 17 < 13^2$$ This concludes the lemma.

Then, we must prove that for every composite $n$ there is a prime $p$ with $n < p < n^2$. Take the largest prime less than $n$ and call that $p_m$. Then by applying the lemma we find that there is some prime $p$ such that $$p_m < p < p_m^2.$$ Because $p > p_m$, $p_m$ is the largest prime less than $n$, and $n$ is composite, we find that $$p < n.$$ Also, we have $$p < p_m^2 < n^2,$$ so we reach the second conclusion: if $n$ is composite then there's a prime $p$ such that $$n < p < n^2.$$

Now we've proved the original statement for both prime and composite $n$, and the proof is complete.

  • 2
    $\begingroup$ Unfortunately, proving that $\pi(n)\approx\frac n{\log n}$ - much less explicit bounds of that form - is substantially harder than simply proving the proposition itself. $\endgroup$ – Steven Stadnicki Jan 2 '16 at 23:40
  • $\begingroup$ Oh, I see. So using the Prime Number Theorem and related results (like the inequalities I used) would count as a "strong theorem" according to the OP? I suppose so. $\endgroup$ – feralin Jan 3 '16 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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