6
$\begingroup$

Is there any method to solve for integer solution of a quadratic equation like following:

$$ax^2 + bx + c = 0$$ where $a, b, c \in \mathbb{Z}$

If not is it possible for the Special case: ?

$$x^2 -x + c = 0$$ where $c \in \mathbb{Z^+}$

I will prefer to have a analytical solution if it exists, other wise a polynomial time solution is also welcome (if it exists).

Note: I've put $c \in \mathbb{Z^+}$ for your convenience. It's also fine if some one can give a solution for $c \in \mathbb{Z}$

$\endgroup$
  • $\begingroup$ You want to find integer roots? $\endgroup$ – Alice Ryhl Dec 2 '14 at 14:21
  • $\begingroup$ yes @KristofferRyhl $\endgroup$ – aroyc Dec 2 '14 at 14:24
  • $\begingroup$ Is pseudo code that finds integer roots if they exist ok? $\endgroup$ – Alice Ryhl Dec 2 '14 at 14:25
  • $\begingroup$ I'm not much worried about code..my exact question is about existence of any well defined non-heuristic algo $\endgroup$ – aroyc Dec 2 '14 at 14:27
  • $\begingroup$ I was hoping you said $c < 0$ $\endgroup$ – Chinny84 Dec 2 '14 at 14:32
6
$\begingroup$

For a general polynomial, $a_0+a_1x+\dots+a_nx^n$, with integer coefficients, you may find all rational roots as follows.

If a root is $x=\frac pq$, with coprime $p,q$, then

$$a_0q^n+a_1pq+\dots+a_np^n=0$$

Thus $p$ is a divisor of $a_0$ and $q$ is a divisor of $a_n$. You have thus a finite number of solutions for both $p$ and $q$: respectively all divisors of $a_0$ (up to sign) and all divisors of $a_n$. It's absolutely free of any heuristic. However, there may be many cases to check if $a_0$ or $a_n$ is a highly composite number, and anyway, you have to factor them first.

And of course, if the $a_i$ share a common factor, you should factor it out first to reduce the computation (this is easy with GCD).

To find only integer roots, consider only $q=1$ in the above.

$\endgroup$
  • 1
    $\begingroup$ It is not an entirely general polynomial: you must (still) assume it has integer coefficients (multiply by a common denominator to get here in case of rational coefficients). And of course in the rare case that all coefficients $a_i$ share a common factor, one can start by dividing by that to limit the search a bit. $\endgroup$ – Marc van Leeuwen Dec 2 '14 at 15:58
  • $\begingroup$ @MarcvanLeeuwen Yes, integer coefficients. I didn't write this as it's a condition in the question, but for the reader it's better to add this. Thank you for pointing this out. $\endgroup$ – Jean-Claude Arbaut Dec 2 '14 at 16:04
5
$\begingroup$

Let $\alpha$ and $\beta$ be the 2 solutions of a quadratic equation $ax^2+bx+c=0$ $$\alpha=\frac{-b+\sqrt{b^2-4ac}}{2a}$$ $$\beta=\frac{-b-\sqrt{b^2-4ac}}{2a}$$

$b^2-4ac$ is known as the discriminant (D). If $D>0$ and is a perfect square, roots are distinct and rational (may not be integers). If D is not a perfect square, roots are distinct and irrational. If $D<0$, roots are imaginary. If $D=0$, $\alpha=\beta=\frac{-b}{2a}$

So, in your case, it depends on the value of c.

$\endgroup$
0
$\begingroup$

I think this answer is unique from the above.

First, rewrite the quadratic as:

$$ 2^\alpha{}ijx^2+bx+2^\theta{}kl=0 $$

The quadratic formula tells us this has roots:

$$ x=\frac{-b\pm\sqrt{b^2-2^{\alpha{}+\theta{}+2}ijkl}}{2^{\alpha+1}ij} $$

Expressing as a difference of squares yields:

$$ b^2-(2^{\alpha+1}ijx+b)^2=2^{\alpha{}+\theta{}+2}ijkl $$

The integer solutions of this are:

$$ \begin{eqnarray} b&=&\pm{}\frac{2^{\alpha{}+\theta{}}ijkl+f^2}{f}\\ 2^{\alpha+1}ijx+b&=&\pm{}\frac{2^{\alpha{}+\theta{}}ijkl-f^2}{f} \end{eqnarray} $$

where $f$ is any integer factor of $2^{\alpha{}+\theta{}}ijkl$. Specifically, choose $f=2^\beta{}ik$ where $\alpha\le\beta\le\theta\le\alpha+\theta$. Solving for $b$ we get:

$$ \begin{eqnarray} b_+&=&2^{\beta}({2^{\alpha{}+\theta{}-\beta}jl+ik})\\ b_-&=&-2^{\beta}({2^{\alpha{}+\theta{}-\beta}jl+ik}) \end{eqnarray} $$

Solving for $x$ we get:

$$ \begin{eqnarray} x&=&\frac{\pm{}(2^{\alpha{}+\theta{}}ijkl-f^2)\mp{}(2^{\alpha{}+\theta{}}ijkl+f^2)}{2^{\alpha+1}ijf}\\ x_+&\in&\left\{-\frac{2^{\theta{}}kl}{f}=-2^{\theta{}-\beta}\frac{l}{i},\frac{-f}{2^{\alpha}ij}=-2^{\beta{}-\alpha}\frac{k}{j}\right\}\\ x_-&\in&\left\{\frac{f}{2^{\alpha}ij}=2^{\beta{}-\alpha}\frac{k}{j}, \frac{2^{\theta{}}kl}{f}=2^{\theta{}-\beta}\frac{l}{i}\right\} \end{eqnarray} $$

For completeness, note that $k=mj$ and $l=ni$, so the solution set for $a$, $b$, and $c$, is:

$$ \begin{eqnarray} a &=& 2^\alpha{}ij\\ b&=&\pm 2^{\beta}ij({2^{\alpha{}+\theta{}-\beta}n+m})\\ c&=&2^\theta{}ijmn\\ x_+&\in&\left\{-2^{\theta{}-\beta}n,-2^{\beta{}-\alpha}m\right\}\\ x_-&\in&\left\{2^{\beta{}-\alpha}m, 2^{\theta{}-\beta}n\right\} \end{eqnarray} $$

where $i$,$j$,$m$,and $n$ are odd and $0\le\alpha\le\beta\le\theta\le\alpha+\theta$.

$\endgroup$

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.