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

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

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.

• 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. – Marc van Leeuwen Dec 2 '14 at 15:58
• @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. – Jean-Claude Arbaut Dec 2 '14 at 16:04
• Thank you very much. – Sebastiano Jan 16 at 22:03

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.

I think this answer is unique from the above.

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