0
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ I had asked a similar question before. math.stackexchange.com/questions/3831521/… Essentially, the method is to solve the Diophantine Equation $y^2 = ax^2 + bx + c$ by transforming it to a Pell Equation and using one of the methods for solving Pell Equations. $\endgroup$
    – vvg
    Jul 15, 2023 at 1:21
  • 1
    $\begingroup$ @vvg Thanks for linking your question. I am wondering, do you think the constraints I placed on $a,b,c$ make the equation in my case any easier to solve than the general case for arbitrary $a,b,c$? The 2nd post provides a quick method for $4x^2+4kx-p$ and mine is something like $4jx^2+4kx-p$. Also, looking at your question it seems you are actually attempting to solve the equation. I am content with a method that only says "yes" or "no" to a quadratic yielding perfect squares; I am not bent on actually solving for the particular $x$ that generates a perfect square. $\endgroup$
    – J W
    Jul 15, 2023 at 1:31
  • 1
    $\begingroup$ Multiply by $4a$ and you get $(2ax+b)^2+4c-b^2=4ay^2$$ or $$u^2-4ay^2=4c-b^2,$ where $u\equiv b\pmod{2a}.$ Obviously, if $b$ is even, we can cancel a factor of $4.$ $\endgroup$ Jul 15, 2023 at 1:53
  • 2
    $\begingroup$ @JohnOmielan : yes, indeed. $\endgroup$
    – vvg
    Jul 15, 2023 at 2:00
  • 3
    $\begingroup$ Solving $x^2-dy^2=n$: if $d$ is a square, this reduces to factoring $n$, which is simple conceptually but can be difficult as a practical matter if $n$ is large. If $d$ is not a square, and $n$ is "small" (I think that means if $n<2\sqrt d$, but I may be misremembering), then solutions come from the continued fraction expression for $\sqrt d$ – again, conceptually simple, but can be computationally challenging for large $d$. If $n$ is not small, things get more difficult. The standard reference is Chrystal's Algebra. $\endgroup$ Jul 15, 2023 at 12:44

1 Answer 1

1
$\begingroup$

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

the Hasse principle, is the idea that one can find an integer solution to an equation by using the Chinese remainder theorem to piece together solutions modulo powers of each different prime number.

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.

$\endgroup$
2
  • $\begingroup$ Thank you! I have implemented this method and it works well enough for my purposes. However, it is quite slow sometimes. Are you aware of a way to quickly check whether or not $ax^2+bx+c$ will be a perfect square given a particular value of $x$ without actually plugging in $x$ and testing the square root? Square root and square root w/remainder become very expensive operations as the numbers get larger. I am hoping to be able to speed up this process by efficiently being able to check if $f(x)$ will be a perfect square for given $x$ without naively plugging and checking. $\endgroup$
    – J W
    Jul 22, 2023 at 4:47
  • 1
    $\begingroup$ @J W: I had given an answer (math.stackexchange.com/q/4592541) to a somewhat related question. In cases where your polynomial is monic i.e., $a=1$, you can use that result from Masser. (Reference in cited answer). For general quadratic polynomials, you need to solve a variant of Pell equations. $\endgroup$
    – vvg
    Jul 22, 2023 at 5:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .