# Deciding whether an integer polynomial has an integer root

This is a question written by my instructor Z. Loria .

Consider the following problem: Given a polynomial $$p(x) = \sum_{i=0}^n a_ix^i$$, where $$a_i$$ are integers, is there a natural number $$n \in \mathbb{N}$$ such that $$p(n) = 0$$?

Show that this problem is decidable by presenting an algorithm in pseudocode that always either outputs such an $$n$$, or stops in finite time and declares that no such $$n$$ exists.

I've to present the above algorithm.

The naïve approach will be to iterate through all the possibilities, but the problem is that it never terminates when the polynomial has no integer roots.

I was thinking about finding some upper bound on the value of $$x$$ and only then iterate through all the possibilities (accept if found, decline if not).

I vaguely remember that for polynomials in that form we can find some $$x$$ such that $$|p(x)|$$ only grows, but I'm not sure how to do it.

• Hint, $p(x)$ is basically $a_nx^n$ when $|x|$ is large enough. Mar 22 at 13:26
• You are in the right track. Try to (algebraically) find a value for $x$ large enough so that $|P(x)|$ only increases after it Mar 22 at 13:46
• Maybe start with doing a few examples and plotting them out (on Desmos for example) Mar 22 at 13:47
• We require you to credit the original source of all copied/quoted material: cs.stackexchange.com/help/referencing. I have given you this feedback before: cs.stackexchange.com/questions/140887/…
– D.W.
Mar 23 at 6:28
• Credit the author -- which means the instructor of that course. If there is a publicly available copy of the assignment, link to it.
– D.W.
Mar 24 at 17:11

(Let's call the root $$\xi$$, because $$n$$ here means the degree of the polynomial. That's seriously bugging me about the question.)

The secret is in noticing that it's easy to test if $$\xi$$ is a root, since you just evaluate the polynomial, but you only need to test a finite number of candidates.

As a first observation, if $$\xi$$ is an integer root of the polynomial, then $$\left| \xi \right| \le \left| a_0 \right|$$, so you only need to test $$2\left| a_0 \right|+1$$ candidates. In fact, you can do better than this because $$\left| \xi \right|$$ must be a factor of $$\left| a_0 \right|$$ by the rational root theorem. So you need only test the factors (both positive and negative) of $$a_0$$. Either way, a finite number of candidates.

As a second observation, if

$$\sum_{i=0}^{n} a_i\,\xi^i = 0$$

Then for any positive integer $$m$$

$$\sum_{i=0}^{n} a_i\,\xi^i \cong 0\mod m$$

So, for example, if

$$\sum_{i=0}^{n} a_i\,2^i \not\cong 0\mod 3$$

then there cannot be a root of the polynomial $$\xi$$ such that $$\xi \cong 2 \mod 3$$.

Conversely, suppose that for two different coprime moduli $$m_1$$ and $$m_2$$, you find all integers $$0 \le \xi_j < m_1$$ and $$0 \le \upsilon_k < m_2$$ such that

$$\sum_{i=0}^{n} a_i\,\xi_j^i \cong 0\mod m_1$$

and

$$\sum_{i=0}^{n} a_i\,\upsilon_k^i \cong 0\mod m_2$$

then you can use the Chinese remainder theorem to find all $$0 \le \psi_l < m_1 m_2$$ such that

$$\sum_{i=0}^{n} a_i\,\psi_l^i \cong 0\mod m_1 m_2$$

This is an important optimisation in practice (i.e. in real computer algebra systems) because evaluating the polynomial might require large integer arithmetic since intermediate values may be larger than a machine word. Using this technique, you can use word-sized integer operations to eliminate a lot of candidates.

$$|ax^3+bx^2+cx+d|>0$$ is equivalent to

$$\left|1+\frac bax^{-1}+\frac cax^{-2}+\frac dax^{-3}\right|>0.$$

Clearly, the limit of the LHS is $$1$$, and by continuity, there will be a finite $$X$$ such that $$x>X$$ implies the above inequality. This generalizes to any degree.

You can take

$$X>\max\left(\left|\frac{3b}a\right|,\sqrt{\left|\frac{3c}a\right|},\sqrt{\left|\frac{3d}a\right|}\right).$$

If $$a_n = 1$$, then all integer roots are divisors of $$a_0$$, either positive or negative, and all other roots are irrational or complex. The integer roots can often be found quite quickly.

It's only slightly more difficult if $$a_n ≠ ± 1$$: Multiply each coefficient by $$a_n^{n-1}$$, then let $$y = x \cdot a_n$$ or $$x = y / a_n$$. You get an equation for y with the highest coefficient $$a_n = 1$$. You find all the integer solutions for y. The rational solutions for x are $$y / a_n$$, and you pick those that are integers.

• $a_0 = -x\sum_{i=1}^n a_ix^{i-1}$. If $x$ is an integer root, $x$ divides $a_0$. Mar 23 at 10:14