For $n \equiv 1 \pmod 3$,there exists $m<n$ such that $n+3k=m^2$

Question

Let $n$ (greater than $1$) be of the form $3k + 1$.
Let $k_1$ be the smallest positive integer such that $$n + 3k_1 = n^2.$$ Let $k_2$ and $m$ be the smallest non negative integers for which $$n + 3k_2 = m^2.$$ Prove that $k_2 < k_1$.

I can verify that easily taking various values of $n$ satisfying $3k+1$ format, but am clueless as to how to prove it. For example, when $n = 7$, adding $3$ fourteen times yields $49$ but adding it three times yields $16$.

Answer 1

Intuitively, the answer is that between $n$ and $n^2$, there are several numbers that are perfect squares, and we only need to find one that is not divisible by $3$.

---

Let's look at all the integers greater than $\sqrt{n}$ and smaller than $n$, i.e., the set

$$S=\{m\in\mathbb N| \sqrt{n} < m < n\}.$$

Since we can safely assume that $n>8$ (we already proved the statement for $n=1,4,7$, we know that $n-\sqrt{n}> 5$, there are certainly $3$ consequtive integers, $n_1,n_2,n_3$, that are all in that set $S$.

Since the two integers are consequtive, they have different remainders modulo $3$. Without loss of generality, let's say $n_1 = 3k' + 1$. Then, $n_1^2 = 3k'^2 + 6k' + 1$.

Therefore, $$n_1^2 = 3k'^2 + 6k' + 1 = 3k + 1 + 3k'^2 + 6k' - 3k = n + 3(k'^2 + 2k'-k)$$

Now we can simply set $K = k'^2 + 2k' - k$ and conclude:

1. Since $n+ 3K = n_1^2$, we must have $k_2\leq K$ (because $k_2$ is the smallest integer satisfying that condition)
2. Since $n_1^2 < n^2$, we must have $K<k_1$. This is because $3K = n_1^2 - n < n^2-n = 3k_1$.

From the points above, we conclude $k_2<k_1$.