Given an $m$ how to find $k$ such that $k m + 1$ is a perfect square

Question

Any way other than trying linearly for all values of $k$.

Answer 1

Note that $(m+2)m+1$ is a perfect square. But it is not necessarily the smallest perfect square of the required shape.

We can if $m\ge 3$ do it a little more cheaply with $(m-2)m+1$.

I assume $k=0$ is not allowed!

Answer 2

If $km+1=n^2$ for some $n$ and $k=am+b$ for some $a,b\in\mathbb{Z}$, $0\le b<m$. Then $$k=\frac{n^2-1}{m}=a^2m+2b+\frac{b^2-1}{m}$$ So we can know $k$ is integer if and only if $b^2\equiv 1 \pmod{m} $.

For example, if $b=\pm 1$ we get $k=a^2m\pm 2$ and $km+1=(am\pm1)^2$

Answer 3

There are infinite $k$ such that $km+1$ is a perfect square. One class of infinite solutions is given below.

For a given $m$, choose $k = a^2m + 2a$, i.e. $k = a(am+2)$ where $a \in \mathbb{Z}$. Hence, we get that $$km + 1 = (a^2m+2a)m + 1 = (am)^2 + 2(am) + 1 = (am+1)^2$$