1

Given a polynomial of the form $f(x) = x^2 + ax + b$, where $a$ and $b$ are integer coefficients, is there an efficient algorithm for finding integer values $x$ for which $f(x)$ is a perfect square? That is, for finding all integers $x$ where $f(x) = y^2$ for some integer $y$?

EDITED TO ADD: My apologies for not being clearer before. If it wasn't already obvious, what I'm wondering is whether there is an efficient algorithm, i.e., something better than just trying all possibilities.

For example, an algorithm that finds the smallest such $x > 0$ and which runs in constant time (or at least something better than $O(x)$) would qualify.

Archie
  • 113
  • I think there should be an algorithm. I think there's always only finitely many $x$ such that $f(x)$ is a perfect square. For example, if $a = 1$, then for large $x$, $x^2 < f(x) < (x+1)^2$ and thus $f(x)$ is not a perfect square. Similarly, if $a=3$, then for large enough $x$, $(x+1)^2 < f(x) < (x+2)^2$. So I guess the algorithm could be, for given $a$, initially calculate how large "for large $x$" (this can be done), and then check values under that large $x$. – mathworker21 Nov 11 '19 at 23:59
  • @mathworker21 For *odd* $a$, there is always an integer solution $x$. Kindly see my answer below. – Tito Piezas III Nov 17 '22 at 03:33

3 Answers3

2

$y^2=x^2+ax+b$, $(2y)^2=4x^2+4ax+4b=(2x+a)^2+4b-a^2$, $4b-a^2=(2y)^2-(2x+a)^2$, so we want to express $4b-a^2$ as a difference of two squares.

Such expressions arise from, and only from, factorizations of $4b-a^2$ of the form $4b-a^2=mn$ with $m,n$ both even or both odd; we get $$ 4b-a^2=\left({m+n\over2}\right)^2-\left({m-n\over2}\right)^2 $$ and then $y=(m+n)/4$, $x=(m-n-2a)/4$.

So the algorithm is, compute $4b-a^2$; find all factorizations $4b-a^2=mn$ with $(m+n)/4$ and $(m-n-2a)/4$ both integers; that gives you all the values of $x$ and $y$ that work.

All of these computations take negligible time, except (for very large values of $a$ and/or $b$) the factorization of $4b-a^2$. That can't be helped; if you had a superfast way to find $x$ and $y$, you'd also have a superfast way of factoring large numbers.

Gerry Myerson
  • 179,216
  • Your last comment is intriguing. Given $$x^2+ax+b = y^2$$ for *odd* $a$, then there is a superfast way to find INTEGER $x,y$ namely, $$x = \frac{(a-r)^2-4b}{4r}$$ $$y = \frac{a^2-r^2-4b}{4r}$$ where we set $r=\pm1$, though I don't know if this also implies a superfast way to factor large numbers. – Tito Piezas III Nov 17 '22 at 05:25
  • @Tito, chances are it leads to a trivial factorization like $1\times(4b-a^2)$. – Gerry Myerson Nov 17 '22 at 08:12
  • I did the math this very minute. Alas it was the trivial factorization $1\times(4b-a^2)$. <Sigh.> At least, it is a superfast way to find $x,y$ for odd $a$. – Tito Piezas III Nov 17 '22 at 08:16
0

Your function is: $$ f(x) = x^2+ax+b $$ and you seek the form: $$ y^2 = x^2+ax+b $$ for some integer $y$ to find $x$. We must solve for $x$ hence let us make the quadratic equation equal to zero: $$ 0 = x^2+ax+b-y^2 $$ The solution to this equation (https://en.wikipedia.org/wiki/Quadratic_formula) is: $$ x_{1,2} = \frac{-a\pm\sqrt{a^2-4(b-y^2)}}{2}$$ For this to have a solution in the set of integer numbers the condition $ a^2-4(b-y^2) \geq 0 $ must be satisfied. As you are seeking for integer values of $x$ then you should only check whether the values of $x_1$ and $x_2$ are integer in your algorithm for the given constants in the solution.

One more condition that you could test for integer solutions is whether $ -a\pm\sqrt{a^2-4(b-y^2)} $ is divisible by $2$. If it is then you have your integer solutions.

Here is a flowchart of the algorithm: enter image description here

Dinno Koluh
  • 753
  • @mathworker21 Yes I am searching through all values of $y$. This is better in a way that you have to check if a number is divisible by $2$ in that is all. If you would search through all values of $x$ you would always get an integer answer for which you would have to check if it is a perfect square. It is obviously easier to check if a number is divisible by $2$ rather than if it is a square number. – Dinno Koluh Nov 12 '19 at 09:23
  • @mathworker21 I wouldn't agree with you. When I am checking the divisibility by $2$ I am checking if the number is divisible by $2$ and not if it is an integer because $-a\pm\sqrt{a^2-4(b-y^2}$ can be an integer but if it is not divisible by $2$ then it is not an integer solution for $x$. – Dinno Koluh Nov 12 '19 at 09:51
  • The main advantage of my solution is that for knowing if there exists an answer you just have to check the divisibility by $2$ which is easier than checking if $ x^2+ax+b $ is a perfect square. – Dinno Koluh Nov 12 '19 at 09:52
  • I am not trolling you. I check the divisibility by reading the remainder when dividing by 2. I am not wasting your time, you are wasting your own time. I don't understand why would you be so triggered. If you don't like my answer then don't bother with it. – Dinno Koluh Nov 12 '19 at 16:48
  • We clearly aren't gonna come to an agreement so I will stop here. Good luck! – Dinno Koluh Nov 12 '19 at 16:53
0

In general, the equation,

$$x^2+ax+b =y^2$$

has infinitely many rational solutions given by,

$$x = \frac{(a-n)^2-4b}{4n}$$ $$y = \frac{a^2-n^2-4b}{4n}$$

for any rational $n$. But you want integer $(x,y)$. For odd a, then an obvious choice is $n = \pm 1$ and $(x,y)$ become integers.

Tito Piezas III
  • 54,565