Strategy for finding integral roots for polynomials with large coefficients 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:


*

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

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