There exist infinitely many prime numbers $p≥2$ and there exist positive integers $k,m$ such that $k^2+1=p+m$ I am asking about the validity of the following conjecture:
Conjecture: There exist infinitely many prime numbers $p≥2$ and there exist positive integers $k,m$ such that $k^2+1=p+m$ with $1≤m≤p-1$.
However, I am not able to prove or disprove it.
 A: Following from the comment by Mike Daas that you are asking whether a number $k^2$ falls among $p,\dots 2p-2$: For any suitably large square number $k^2$, we can always pick the largest prime number $p_k<k^2$.
Assume that $k^2>2p_k-2$. Bertrand's postulate assures us that for suitably large $p$, there is at least one prime number in any interval $(p,2p-2)$. So if $k^2$ is not in the interval $(p_k,2p_k-2)$, then there is another  prime number in that interval that is smaller than $k^2$, and $p_k$ is not the largest prime smaller than $k^2$. In other words, every suitably large $k^2$ falls in an interval $(p,2p-2)$.
A: Let's note (usual notation) by $\pi(n)$ - prime counting function and $p_n$-$n$'th prime number. We have
$$p_{\pi (k)} \leq k < p_{\pi (k)+1}$$
or
$$p_{\pi (k^2)} < k^2 < p_{\pi (k^2)+1}$$
We can add $m-1\geq2$ such that
$$p_{\pi (k^2)} <p_{\pi (k^2)} +m-1 =k^2 < p_{\pi (k^2)+1}$$
It has to be $m-1\geq2$, because $m-1=1$ would lead to $p_{\pi (k^2)}=k^2-1=(k-1)(k+1)$ (not a prime for large $k$'s).
Finally, from the strict version of the Bertrand's postulate
$$2\leq m-1 < p_{\pi (k^2)+1}-p_{\pi (k^2)}\leq p_{\pi (k^2)}-2$$

Summary: we have found a subsequence of prime numbers $\left(p_{\pi (k^2)}\right)_{k\in\mathbb{N}}$, $k>1$ satisfying:
$$k^2 +1=p_{\pi (k^2)} +m$$
with $3\leq m\leq p_{\pi (k^2)}-1$. It yields infinite different primes because:

*

*Legendre's conjecture or

*from Bertrand's postulate $$\pi((2\cdot k)^2)=\pi(4\cdot k^2)>\pi(2\cdot k^2)>\pi(k^2) \Rightarrow p_{\pi((2\cdot k)^2)} > p_{\pi(k^2)}$$
whichever version you prefer.
