I have already looked at this post and this post but can't seem to apply completing the square to some cases because the numbers become non-integers.
Given a quadratic equation of the form $$f(x)=ax^2+bx+c$$
$$a,b,c \in \mathbb{Z}$$
$$ a, b, c \neq 0,$$
How can I determine whether or not $f(x)$ will ever yield a value that is a perfect square integer?
The second post I linked has a method of completing the square for equations of the form $4x^2+4kx-p$ which is slightly too specific for my case, but has led me on the right track.
Based on this comment by Andre Nicholas, it appears to be difficult to tackle this problem in the general case for arbitrary $a, b, c$, so I will place some constraints:
In addition to $a, b, c \neq 0$, assume the following:
- $a$ is always a product of two perfect square integers and is therefore always a perfect square itself (i.e., $a = m^2n^2 = (mn)^2$)
- $a,$ $b,$ and $c$ need not divide one another, but $gcd(a,b,c)$ is always a perfect square $\gt 1$
- $c$ is never a perfect square so the trivial case $f(0)$ will never be a perfect square
Take, for example,
$$f(x)=810000x^2-45642249684x+642606171242553$$
$$g(x)=810000x^2-45641877084x+642981810606444$$
$$h(x)=810000x^2-45642751884x+642957163366248$$
The question is, which of these functions will yield a perfect square for at least one $x$, and which will not?
By brute force computation, I have found that $f(29136) = 387846209529$ and $\sqrt{387846209529}=622773$ (perfect square). I failed to find values of $x$ for which $g(x)$ and $h(x)$ yield positive squares, but that does not necessarily mean that there do not exist any, since I only iterated from $x=1$ to $x=10000000$.
I am not sure how (or if it's even possible) to mathematically prove that these functions cannot possibly yield perfect square solutions. Brute force iteration might be able to prove that a perfect-square solution exists, but it cannot disprove the existence of a solution because you cannot iterate to infinity.
I have tried to complete the square as suggested in the linked posts, but am not sure how to evaluate the rewritten quadratic with non-integers.
$$f(x) = 810000x^2-45642249684x+642606171242553$$
$$=$$
$$810000(x-\frac{140871141}{5000})^2-(\frac{1267840269}{50})^2+642606171242553$$
How do I proceed from here to determine whether or not $f(x)$ has any $x$ yielding a perfect square, similar to the $(2n+a+m)(2n+a−m)=b$ method in one of the comments on the 2nd post? The comment author mentions that once in that form, $b$'s prime factorization will yield all perfect-square solutions. However, I am not sure how to extract such a $b$ from the complete-the-square above.
Note: I am not extremely well-versed in math, so I do not fully understand some of the topics mentioned in those other posts like Pell's equations, Cayley-Hamilton theorem, etc.
Best Answer
If you want to check for existence of integer solutions, you can try modular tests. i.e. if $y^2 = ax^2 + bx + c$ has integer solutions then the equation also holds modulo $p \in \mathbb{P}$.
i.e.,
$$ \forall p \in \mathbb{P}, y^2 \equiv ax^2 + bx + c \pmod{p} $$
If we first transform the equation into Pell form using the transformation in this question, i.e.,
$$ X = 2ax + b, \\ Y = 2y $$
to get
$$y^2 = ax^2 + bx + c \rightarrow X^2 - dY^2 = n$$
where $$n = b^2 - 4ac \text{ and } d = a$$
then, we can check if $X^2 \equiv n \pmod{d}$. When $d$ is small or easily factored, this is viable. We could also check $X^2 - dY^2 \equiv 0 \pmod{n}$ if $n$ is small or easily factored or if $d$ is a perfect square.
This is called the Hasse Principle
Example:
Consider the second equation listed in the question:
$$y^2=810000x^2-45641877084x+642981810606444$$
WolframAlpha gives the answer that this equation has no integer solutions. Let us see what our approach gives us.
We have $a = 810000, b = -45641877084, c = 642981810606444$. We apply the transformation
$$ X = 2ax + b = 2*810000x + b = 1620000x -45641877084, \\ Y = 2y $$
to get
$$ X^2 - dY^2 = n $$
where
$$ \begin{align} d & = a = 810000 = 900^2, \\ n & = b^2 - 4ac \\ & = (-45641877084)^2 - 4 \times 810000 \times 642981810606444 \\ & = -80122613914216944 \end{align} $$
So, we need to solve
$$ \begin{align} X^2 - 900^2Y^2 & = X^2 - (900Y)^2 \\ & = -80122613914216944 \end{align} \tag{1} $$
Unfortunately, we cannot use the modulo $d$ trick because $d$ itself is a perfect square. So, $\forall p \in \mathbb{P}$, we will have solutions to $(X-900Y)(X+900Y) = uv \equiv -80122613914216944 \pmod{p}$. So, we cannot use that.
Instead, we use the fact that $(X-900Y)(X+900Y) = uv = -80122613914216944$ and we factor the RHS. Then we can solve for $X,Y$ using the divisors of $-80122613914216944$ (there are 720 divisors in this case).
The only integer solutions to $X,Y$ in Eqn. (1) are:
$$ \begin{matrix} X = 1620000x -45641877084 & Y=2y & x & y \\ -13738445457084 & ±15264939400 & -8508695.885 & ±7632469700 \\ -45642237084 & ±50714572 & -56348.21862 & ±25357286 \\ -3718037916 & ±4143108 & -30469.08333 & ±2071554 \\ -1606902084 & ±1812936 & -29165.91307 & ±906468 \\ 1606902084 & ±1812936 & -27182.08333 & ±906468 \\ 3718037916 & ±4143108 & -25878.91307 & ±2071554 \\ 45642237084 & ±50714572 & 0.222222222 & ±25357286 \\ 13738445457084 & ±15264939400 & 8452347.889 & ±7632469700 \\ \end{matrix} $$
So, even though $X,Y$ are integers, the original variables $x, y$ do not have any integer solutions.
The only caveat with this method is we need to factor $n$ and if $n$ is large, this is going to be very slow. (I used WolframAlpha to get the integer solutions to Eqn. 1.)
Prologue:
Just to illustrate how we can use the modulo trick for Pell equations where $d$ is not a perfect square, consider the example Pell equation $$X^2 - 5Y^2 = 23.$$
Taking modulo $5$ we get $X^2 \equiv 3 \pmod{5}$.
But the only squares modulo $5$ are $$0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 4, 3^2 \equiv 9 \equiv 4, 4^2 \equiv 16 \equiv 1 \pmod{5}$$
i.e.,
$$X^2 \in \{0, 1, 4\} \pmod{5}.$$
Therefore, there are no modular solutions for $X^2 \equiv 3 \pmod{5}$ and that implies there are no integer solutions for $X$ by the Hasse principle.