# Andrica's conjecture implies Legendre's conjecture

Does Andrica's conjecture imply Legendre's conjecture? I have the following reasoning.

Let $p_n$ denote the $n$th prime. Recall that Andrica's conjecture is the following statement: $$\sqrt{p_{n+1}}-\sqrt{p_n}<1,$$

for all positive nonzero integer $n$. On the other hand, Legendre's conjecture states that there is a prime number between $m^2$ and $(m+1)^2$ for every positive integer $m$. I then propose the following Theorem.

Theorem 1. Andrica's conjecture implies Legendre's conjecture.

Proof. Let $g_n$ denote the $n$th prime gap. Following Andrica's conjecture, we have $g_{n}<2{\sqrt {p_{n}}}+1$, or equivalently $p_{n+1}<2{\sqrt {p_{n}}}+1+p_{n}$.

Now let $N$ be a positive integer greater than $2$ and $p_{n}$ the greatest prime smaller than or equal to $(N-1)^2$. We then have:

\begin{align*} (N-1)^2 & < p_{n+1}\\ & < 2{\sqrt {p_{n}}}+1+p_{n} \\ & < (\sqrt {p_{n}} + 1)^2. \end{align*}

But since $p_{n}<(N-1)^2<p_{n+1}$, we have: \begin{align*} (N-1)^2 & < (\sqrt {p_{n}} + 1)^2 \\ & < (\sqrt {(N-1)^2} + 1)^2 \\ & < (N-1+1)^2 \\ & < N^2. \end{align*}

We have therefore shown that assuming Andrica's conjecture, $(N-1)^2<p_{n+1}<N^2$, i.e., that there is always a prime between $(N-1)^2$ and $N^2$ for all positive integer $N>2$. $$\tag*{\square}$$

I recall reading somewhere that one can not imply Legendre's conjecture from Andrica's, so I must be missing something here. What is it?

• You have a typo, "But since $p_n < p_{n+1} < (N-1)^2$" ought to be "But since $p_n < (N-1)^2 < p_{n+1}$", and after that you forgot to mention $p_{n+1}$ so you just state $(N-1)^2 < N^2$. Should be $(N-1)^2 < p_{n+1} < (\sqrt{p_n} + 1)^2$ etc. Yes, Andrica's conjecture implies Legendre's conjecture. – Daniel Fischer Apr 10 '18 at 15:11
• @DanielFischer Thank you, typos corrected. If you post an answer I will accept it. – Klangen Apr 17 '18 at 12:25
• So that means Legendre's conjecture is true for twin primes. – Mr Pie Jan 21 at 9:57

As a matter of style, it is not good that you switch from $m^2$ and $(m+1)^2$ used in the statement of Legendre's conjecture to using $(N-1)^2$ and $N^2$ in the proof, it would be better to use the same notation in both. And I would leave the prime gap $g_n$ out of it and write
\begin{align} (N-1)^2 &< p_{n+1} \\ &= (\sqrt{p_{n+1}})^2 \\ &< (\sqrt{p_n} + 1)^2 \tag{Andrica's conjecture}\\ &\leqslant \bigl((N-1) + 1\bigr)^2 \tag{$p_n \leqslant (N-1)^2$}\\ &= N^2\,. \end{align}