is there an analytic solution to $n^2+kn-d=m^2$ m,n integers

Question

For $k=24,d=-17;m=8,n=3$, completing the square gives $(12+n)^2=m^2+161$ Where $161$ just happens to be the product of two primes $(q=7,p=23)$, so for large $k,m,n$ factoring may be very slow.

Alternatively, a sequence $17..29$ sums to $161$ and has $q=7$ terms, and the first is $2m+1$ and the last is $2q+2m-1$ (always(?)). Also $161 = q(q+2m)$. Obviously(?) $pq=161$ represents a hyperbola. I thought maybe there is a way to transform the equation to an ellipse or circle to make it more manageable, but it appears not so.

If factoring cannot be avoided, what method is most useful for $t>>161$, but $<=256=$digits.

Answer 1

I take it the problem is, given (sizable) $k$ and $d$, find $m$ and $n$ such that the equation in the title holds. As you have seen in your example, this will come down to expressing some number as a difference of two squares. But doing this is just as hard as factoring, so in general you will not find a solution unless you can factor the numbers that arise.

Answer 2

If $n^2 + kn = m^2 + d$, $4n^2 + 4kn = 4m^2 + 4d$ or $4n^2 + 4kn + k^2= 4m^2 + 4d+k^2$ or $(2n+k)^2 = 4m^2 + 4d+k^2$ or $(2n+k)^2 - 4m^2 = 4d+k^2$ or $(2n+k-2m)(2n+k+2m) = 4d+k^2$.

By looking at all the factorizations of $4d+k^2$, all possible values of $n$ and $m$ can be determined.

More explicitly, for each factorization $4d+k^2 = a\cdot b$ with $a \le b$, try to solve $a = 2n+k-2m$ and $b = 2n+k+2m$.

The algebra is easy: $b-a = 4m$ and $b+a = 4n+2k$, so $m = (b-a)/4$ and $n = (b+a-2k)/4$.

To have a solution in integers, $b-a$ and $b+a+2k$ must both be divisible by 4, so $k$ must be divisible by 2.

You can look into the factorization possibilities more deeply, but this should be enough to write an algorithm for any given $k$ and $d$.