Strategy for finding integral roots for polynomials with large coefficients

Question

I'm trying to find the integer roots for $f(x) = x^5 + 47x^4 + 423x^3 + 140x^2 + 1213x - 420 = 0$. The techniques I'm expected to have at my disposal are:

1. For a polynomial with integer coefficients $p(x) = a_nx^n + a_{n-1}x^{n-1}+ \dots + a_1x + a_0$, if $p(x)$ has a rational root $\frac{s}{t}$, then $s|a_0$ and $t|a_n$.
2. "Einstein's Irreducibility Criterion": If there exists a prime $p$ such that $a_{n-1}\equiv_pa_{n-2}\equiv_p\dots\equiv_pa_0\equiv_p0$, $a_n\not\equiv_p0$ and $a_0\not\equiv_{p^2}0$ then $p(x)$ is irreducible over the rationals.

The book gives the answers $-12$ and $-35$. Using the first strategy, I could have solved for every divisor of $-420$ to find one solution $c$, then divide $(x-c)$ into $f(x)$ and perform the same process with the quotient. But is there a less time-consuming way to find these roots? I feel like I'm supposed to simplify $f(x)$ by substituting $x$ with something but I wouldn't know what that is.

Answer 1

Assume $r$ is an integer root.

As you noted, $r$ must be a factor of $420$.

Unfortunately, since $$420=(2^2)(3)(5)(7)$$ there are lots of factors.

The search can be cut down by a few preliminary calculations . . .

Firstly, since $f(1) > 0$, and $f(x)$ is strictly increasing for $x > 0$, it follows that $r$ can't be positive.

If $r$ is even, then $1213r$ is a multiple of $4$, hence $r$ would have to be a multiple of $4$.

If $r$ is a multiple of $3$, we get the congruence $$1213r - 420 \equiv 0\;(\text{mod}\;9)$$ which reduces to $r \equiv 3\;(\text{mod}\;9)$.

If $r$ is a multiple of $5$, we get the congruence $$1213r - 420 \equiv 0\;(\text{mod}\;25)$$ which reduces to $r \equiv 15\;(\text{mod}\;25)$.

If $r$ is a multiple of $7$, we get the congruence $$1213r - 420 \equiv 0\;(\text{mod}\;49)$$ which reduces to $r \equiv 14\;(\text{mod}\;49)$.

That should cut down the testing considerably.

Of course, once you find one root, you can divide it out of $420$.

Thus, once you find the root $r=-12$, it follows that if $s$ is another integer root, then $s$ must divide $$\frac{420}{12}=35$$ But then the congruence conditions leave only one candidate, namely, $s=-35$.

Of course, solving the congruences still involves work, but the numbers are much smaller, and also, it's more fun than just plugging in values of $r$, one after another, into the equation.

Answer 2

In general, there are several algorithms to factor a polynomial $f(x)$ over the integers, which are of polynomial time:

Is factoring polynomials as hard as factoring integers?

So it is not so much time-consuming.

Of course, for the question here, the Rational Root Test certainly is one of the best methods for finding rational roots. This gives $$ f(x)=(x^3+3x-1)(x+35)(x+12). $$ I don't think that you are supposed to do anything else. The divisors of $420$ are quite manageable.

We do not need Eisenstein, because we already found linear factors, so that the polynomial cannot be irreducible.

Answer 3

Try \begin{align} x^5 + 47x^4 + 423x^3 + 140x^2 + 1213x - 420 & \equiv (x^2+ax+b)(x^3+cx^2+dx+e) \\ & \equiv x^5+(a+c)x^4+(ac+b+d)x^3 \\ & \quad +(ad+bc+e)x^2+(ae+bd)x+be \end{align} with different combinations of $b$ and $e$