Find All $x$ values where $f(x)$ is Perfect Square
Is there a formula, method or anyway to find all positive $x$ integer values (if exists) such that $f(x)$ is Perfect square where $f(x)$ is a quadratic equation?
For example if I have the following function:
\begin{align*}
f(x)= 4x^2+84x-15
\end{align*}
Then I need all integer x values which makes $f(x)$ Perfect Squares.
I know for this equation $x \in \{2,10,19,47\}$ but I knew this by guessing, I mean I wrote a program in java and I traversed all of x values from 1 to 1000 and I got this set of x values that gives me a perfect square, I am not sure if I have to go further and what is the bound to do this guessing. But I am not interested in such method.
I am interested in a generalization for this problem (if possible) where I need to know all x values which makes $f(x)$ square where:
\begin{align*} f(x) = ax^2+bx+c \tag{1} \end{align*}
where \begin{align} a,b,c \in \mathbb Z \end{align}
Update 1
I have found a way from my derived equations of my research where I can find \begin{align*} x_i \, | \ \sqrt{f(x_i)}\in \mathbb Z \end{align*} \begin{align*} where\ i=1,2\ and\ x_1 > x_2 \end{align*} The question now, is there a way to use $x_1,x_2$ to find any other $x_i$ (if exist) \begin{align*} where \quad i>2 \ \ and\ \ 0 < x_i < x_2 \end{align*}
For the mentioned example, I know that the equation has $x_1 = 47$ and $x_2 = 19$, is there a way to find $ 0 < x_3 < 19 $ if $x_3$ exists from the known $x_1$ and $x_2$?
Update 2
After reading @ColmBhandal note I am trying in this update to transform the original equation to another equation. Resolving the new equation will resolve the previous equation.
Since $a$ in my case is always square then to get $x$ where $f(x)$ a perfect square we need to resolve the following: \begin{align*} bx+c=2nsx+n^2\ where\ s=\sqrt{a},\ n >= 1, n\in\mathbb Z \end{align*} Therefore \begin{align*} x=g(n)=\frac{n^2-c}{b-2sn}\tag{2} \end{align*} Now this is a Diophantine equation in the following form (assign $x=Y$ and $n=X$): \begin{align*} X^2-bY+2sXY-c=0\tag{3} \end{align*} Now we need to find $n$|$n>1\ and\ n\in\mathbb Z$ which makes $g(n)\in\mathbb Z$.
Let's note the following:
- $n$ has min value when $numerator = denominator$ (this happens to get $n=1$)which is \begin{align*} n^2-c = b-2sn \end{align*} \begin{align*} n^2+2sn-b-c = 0\implies\ n>= \Bigg\lceil {\frac{-(2s)+\sqrt{(2s)^2-(4(-b-c))}}{2}}\ \Bigg\rceil \end{align*}
- $n$ has a max value when the $denominator=0$ which is \begin{align*} b-2sn=0\implies n < \frac{b}{2s} \end{align*}
- We can get the first biggest two $n$ values because we know $x_1$ and $x_2$.
So for the mentioned example since $a=4$ then $s=2$ which lets $x=g(n)$ is \begin{align*} g(n)=\frac{n^2+15}{84-4n}\quad where\ n\in\mathbb Z, 7<=n<21 \end{align*} We also know that $n_1=19\ and\ n_2=17$ because $x_1=47\ and\ x_2=19$ so actually we are looking for $n$ (if exists) \begin{align*} 7<= n < 17\ |\ n\in\mathbb Z \end{align*}
So we need now the integer solutions for this equation. I hope this equation now could be resolved, I think it is a Diophantine Equation and we need integer solutions for it because the equation looks like: \begin{align*} x^2-84y+4xy+15=0 \end{align*}
Update 3
After reading this paper, I found (on page 6) that equation (3) could be transformed to
\begin{align*}
(bx + e)(by + d) = ed − bf
\end{align*}
Then writing $ed − bf = N$ and if $N$ is not zero (which is in our case) then we can factorize N to get all integer solutions.
Unfortunately, This means that my new Diophantine Equation number (3) should be resolved by factoring.
My question now is this the only way to solve such equations?
Is there a way to solve equation (1) or (3) without completing the square or factoring a number to get solutions?
Notes:
- Completing the square method and solving Pell's equation needs at the end of the day to do factoring and because in my case the coefficients could be 40-50 digits numbers, factorization couldn't be a solution. I am looking for a generalization for the problem and write a computer program to solve such equations with a very large coefficients.
- Therefore any method that needs factorization or to iterate linearly to find the solutions are not helpful.
- I don't really know what tags I have to give for this question so please correct my tags if I missed or messed something. Thanks.
Solution 1:
Try these monsters:
$x_{n_1}=\frac{1}{2a}\left[\frac{\gamma_0 \sqrt{P^2-1}+Q\beta_0}{2\sqrt{P^2-1}}\cdot \left(P+\sqrt{P^2-1}\right)^n+ \frac{\gamma_0 \sqrt{P^2-1}-Q\beta_0}{2\sqrt{P^2-1}}\cdot \left(P-\sqrt{P^2-1}\right)^n-b\right]$
and
$x_{n_2}=\frac{1}{2a}\left[\frac{\gamma_0 \sqrt{P^2-1}-Q\beta_0}{2\sqrt{P^2-1}}\cdot \left(P+\sqrt{P^2-1}\right)^n+ \frac{\gamma_0 \sqrt{P^2-1}+Q\beta_0}{2\sqrt{P^2-1}}\cdot \left(P-\sqrt{P^2-1}\right)^n-b\right]$
6 notes:
- $(a,b,c)$ from $f(x)=ax^2+bx+c$
- use minimal $(P,Q)$ such that $P^2-aQ^2=1$
- use minimal $(\gamma_0,\beta_0)$ such that $a\gamma_0^2-\beta_0^2=a(b^2-4ac)$
- for non-square $a$, when a is a square it's analogous to the explanation below
- Reasoning for $x_{n_1}$ and $x_{n_2}$ is that some solutions to $ \ a\gamma^2-\beta^2=a(b^2-4ac) \ $ have two separate strands.
- In using this as written, it may be that you need to take every $ \ n=2m \ $ or $ \ n=2m-1 \ $ or multiples $n=km$ to meet the $\gamma-b \equiv 0 \pmod {2a}$ constraint (referring to how $ \ 2a \cdot x + b = \gamma \ $ below)
The derivation of the above is arriving at the pell equation: $$\begin{align} ax^2 + bx + c &= f(x)=\alpha^2 \\ a(x+b/2a)^2-\frac{b^2-4ac}{4a} &=\alpha^2 \\ a(2ax+b)^2-a(b^2-4ac)&=4a^2\alpha^2=\beta^2 \\ a\gamma^2-\beta^2&=a(b^2-4ac) \end{align}$$ And solving using standard techniques.Thus $$x_n=\frac{\gamma_n-b}{2a}$$ Such that $\gamma_n$ is the nth solution in the above pell type equation : $a\gamma^2-\beta^2=a(b^2-4ac)$
An explanation as to why in your first problem $(2,10,19,47)$ are the only answers is what follows:
The problem at the top has $(a,b,c)=(4,84,-15)$. Since $a$ is square, that pell equation morphs into a difference of two squares.
$$ \begin{align} 4\gamma^2-\beta^2&=29184 \\ (2\gamma)^2-\beta^2&=29184=2^9\cdot3\cdot19 \end{align}$$
Using this identity: $$\left(\frac{d_1+d_2}{2}\right)^2-\left(\frac{d_1-d_2}{2}\right)^2=d_1\cdot d_2$$
Let $d_1, d_2$ be two divisors (of the same parity) of $29184$. You can see here that since there can only be a limited number of divisors of $29184$, even more so limited that have the same parity, you know right here that there's going to be a limited number of solutions.
Let $2\gamma=\frac{d_1+d_2}{2}$, thus $\gamma=\frac{d_1+d_2}{4}$, and finally putting this back into our $x$, and letting $b=84$ and $a=4$, arrive at
$$x=\frac{\left(\frac{d_1+d_2}{4}\right)-84}{8}$$ or $$x=\frac{d_1+d_2-336}{32}=\frac{d_1+d_2}{32}-\frac{21}{2}$$
Now we observe that both factors must add to something directly proportional to 16:
$$d_1+d_2=16\cdot k$$
for the fraction $21/2$ to become whole when added. This implies that both $d_1$ and $d_2$ need to have a factor of atleast $2^4$. The only two-factor sets that come from $2^9\cdot3\cdot19$ and meet this requirement are:
$$\begin{align} (d_1,d_2) &\to x(d_1,d_2) &&\to x=\frac{d_1+d_2}{32}-\frac{21}{2} \\ \cdots \cdots \cdots \cdots \cdots \cdots \\ (3\cdot 19 \cdot 2^4, 2^5) &\to x(912,32) &&\to x=19 \\ (3\cdot 19 \cdot 2^5, 2^4) &\to x(1824,16) &&\to x=47 \\ (3\cdot 2^4,19 \cdot 2^5) &\to x(48,608) &&\to x=10 \\ (3\cdot 2^5,19 \cdot 2^4) &\to x(96,304) &&\to x=2 \\ \end{align}$$