21
$\begingroup$

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:

  1. $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*}
  2. $n$ has a max value when the $denominator=0$ which is \begin{align*} b-2sn=0\implies n < \frac{b}{2s} \end{align*}
  3. 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.
$\endgroup$
  • 2
    $\begingroup$ $p, s - $ it solutions of Pell equations. Their finding is standard procedure. $\endgroup$ – individ Sep 14 '15 at 13:39
  • 5
    $\begingroup$ For such cases when the coefficients of the squares. It all comes down to a difference of squares. $$y^2=4x^2+84x-15=4x^2+84x+441-456=(2x+21)^2-456$$ $$456=(2x+21-y)(2x+21+y)$$ Need the number $456$ be decomposed into all possible combinations of multipliers and solve linear equations. $\endgroup$ – individ Sep 14 '15 at 15:27
  • 2
    $\begingroup$ Nothing do not have to guess. Factorization is a standard procedure. Solution of system of linear equations the same difficulty no. $\endgroup$ – individ Sep 14 '15 at 17:27
  • 6
    $\begingroup$ @Zrieq Solving your problem is equivalent to factoring $456$, for any solution $(x,y)$ gives you a factorization $(2x+21-y)(2x+21+y)$. $\endgroup$ – Hagen von Eitzen Sep 14 '15 at 17:52
  • 3
    $\begingroup$ @Zrieq: You miss the point: solutions to your problem give you factorizations of $N$. If $N$ is a number that's too hard to factor, then solving your problem is too hard. If it turned out there was a better way to solve your problem than factoring, then people would devise new factoring algorithms that work by setting up and solving problems if the type you ask about; and once that happens, we are right back to the situation where the best way to solve your problem is to factor. $\endgroup$ – Hurkyl Sep 19 '15 at 13:23
4
$\begingroup$

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:

  1. $(a,b,c)$ from $f(x)=ax^2+bx+c$
  2. use minimal $(P,Q)$ such that $P^2-aQ^2=1$
  3. use minimal $(\gamma_0,\beta_0)$ such that $a\gamma_0^2-\beta_0^2=a(b^2-4ac)$
  4. for non-square $a$, when a is a square it's analogous to the explanation below
  5. 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.
  6. 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}$$

$\endgroup$
  • $\begingroup$ @AmateurMathGuyThanks for your answer, but we already have in the comments of the question that we already know about pell equations, which will solve such equation. However, using pell equation still needs factorization ... So I am leaving this question to make someone think with me of a solution without using factorization nor iterating solutions as this is my question in the first place. $\endgroup$ – Zrieq Aug 17 '17 at 22:10
  • $\begingroup$ You're welcome and you have my apologies once again, I became aware right as I was finishing up the response, that you weren't looking for anything with factoring or iterating. I'll keep your question in mind for the future. $\endgroup$ – AmateurMathPirate Aug 17 '17 at 22:25
  • $\begingroup$ @Zrieq Would a function, such that the input were the natural numbers and the output were x values making a quadratic a square, would that answer your question? Reason I ask is that I don't see any iteration or factoring if all you're doing is inputting naturals...40 digit numbers aside... $\endgroup$ – AmateurMathPirate Aug 25 '17 at 17:26
  • $\begingroup$ For some reason I am unable to mention you using @ in the beginning of the comment ! @AmateurMathGuy I didn't get what you mean. Can you please explain more? $\endgroup$ – Zrieq Aug 26 '17 at 20:33
  • $\begingroup$ @Zrieq Sure, and bear with me if this is something that you've come across already, but, the first equation in my response, the pell equation, does lead to a second order recurrence relation in x, but that recurrence is readily solvable, (given that you know the first two x terms in the sequence, perhaps your main objection, I know), so if you know the first two x values that make the quadratic output a square, you can know the rest. If you want, I can give you the formula, perhaps you know it already, but I can show you a formula with an arbitrary first two x values that you can input. $\endgroup$ – AmateurMathPirate Aug 27 '17 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.