Given an $m$ how to find $k$ such that $k m + 1$ is a perfect square Any way other than trying linearly for all values of $k$. 

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$
