1

Let's say I have a quadratic equation, $x^2+kx+a-kb=0$, with $a$ and $b$ as known constants (e.g. $a=25$ and $b=86$), and $k$ a parameter that I wanna tune. The solution is $x=\frac{-k \pm \sqrt{k^2-4(a-kb)}}{2}$.

Let's say I wanna find the smallest $k$ such that $\sqrt{k^2-4(a-kb)}$ is an integer. In other words, I want $k^2-4(a-kb)$ to be a square number. In the example of $a=25$ and $b=86$, then $k=50$ and $\sqrt{k^2-4(a-kb)}=140$.

Is there an algorithm to find such $k$, better than brute force?

Pannocchia
  • 11
  • Let $k^2-4(a-kb)=x^2$, we have $(k-x)(k+x)=4(a-kb)$. We don't have an algorithm for that, but made a little progress: try to make 4(a-kb) a product of two numbers being equally distant from k. – Miles Zhou Oct 09 '18 at 03:10

1 Answers1

1

You want

$$k^2+4kb-4a=y^2$$

$$k^2+4kb+4b^2-y^2=4(b^2+a)$$

$$(k+2b)^2-y^2=4(b^2+a)$$

$$(k+2b-y)(k+2b+y)=4(b^2+a).$$

In particular, if $mn=b^2+a$ with $m>n$, you can take

$$k+2b-y=2n,k+2b+y=2m \implies 2k+2b=2m+2n\implies k=m+n-2b.$$

The smaller values of $k$ occur when $m$ and $n$ are close. So, if you can find the factorization of $b^2+a$ into two parts as close together as possible,* you will get the minimal value of $k$.

In your example, $b^2+a=7421=41\cdot 181$. This gives $k=41+181-2\cdot 86=50$, which is the same as what you got.

*To find such a factorization, try using Fermat's factorization method. This should be decently fast if $b^2+a$ is small, and will give you the best such factorization for your purposes.

Carl Schildkraut
  • 32,931