Is there any methods to solve for integer solution of a quadratic equation like $ax^2 + bx + c = 0$

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}$

Solution 1:

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.

Solution 2:

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.

Solution 3:

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$.