"Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime between $n^2$ and $(n + 1)^2$ for every positive integer $n$" (https://en.m.wikipedia.org/wiki/Legendre%27s_conjecture)

But there is also the proofed Bertrand's postulate:
"Bertrand's postulate is a theorem stating that for any integer $n > 1$, there always exists at least one prime number $p$ with $n < p < 2n$"

My problem is that, with Bertrand's postulate, it seems logical that the Legendre's conjecture is also true, because the range from $k$ to $2k$ is smaller then the range from $n^2$ to $(n+1)^2 = n^2 + 2n + 1$. So if you choose $k = n^2$ there will always be a prime.

But until now the conjecture of Legendre is unproved, that's why I probably made a thinking error. But I don't know where the mistake in my logic is.


2 Answers 2


Actually$$\frac{(n+1)^2}{n^2}=1+\frac2n+\frac1{n^2}<2$$if $n>2$. In other words, $(n+1)^2<2n^2$ if $n>2$. So, in fact, the gap is smaller.

  • $\begingroup$ Okay thank you ! But what is if you choose $k = n^2$. You have the range $k$ to $2k$ and the range $n^2 = k$ to $(n+1)^2$. Will there be necessarily a prime in the last interval ? $\endgroup$
    – Matti
    Jul 30, 2019 at 10:33
  • 1
    $\begingroup$ If I knew the to this question, I would have proved Legendre's conjecture, right?! $\endgroup$ Jul 30, 2019 at 10:36

Your confusion is that $2n+1$ means less and less as $n$ increases by $n=201$ it adds under 1 percent. By the time you hit 20001, you get it means under 1 part in 10000, compared to $n^2$ . Asymptotically, it means nothing. By $n=4$ you've surpassed the more accurate restatement of Bertrand's postulate of, there's always a prime between $x$ and $2x-2$ for $x>3$

  • $\begingroup$ in fact Legendre's conjecture can be restated as there's always a prime between $d$ and $d+4\lfloor\sqrt{d}\rfloor+3$ if $d$ is nearby a square number. $\endgroup$
    – user645636
    Oct 13, 2019 at 15:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .