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}$
 A: 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.
A: 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$.
A: 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.
