# Polynomials Shouldn't Have factors using Rational Root Theorem but it does!

I came across this polynomial

$X^4 + X^3 + 2X^2 + X + 1$

I tried to factor it using Rational root theorem, but it seems there are no roots possible. 1 or -1 don't work.

But I know for a fact that its composed of $(X^2 + X + 1) * (X^2 + 1)$ Wolfram Alpha factored it properly but can't seem to generate a step by step solution so I can understand what method was used?

I need 2 things:

1. A test that can tell me if this is factorizable.
2. A method to factor it.
-
Well, one can extend the Rational Root Theorem and note the polynomial has root $i$. But that does not answer your general question. –  André Nicolas Jul 5 '14 at 15:02
The "contradiction" implicit in your title is not a contradiction. The rational root theorem only gives you rational factors of the form $(X-r)$ where $r$ is rational. As you will see by finding the roots of $X^2+1$ and of $X^2+X+1$, your polynomial indeed has no rational roots. –  Lee Mosher Jul 5 '14 at 15:04
@LeeMosher ya that makes sense, can you answer the questions thought? that would be awesome? –  Tamim Salem Jul 5 '14 at 15:09
Follow this link to get information, particularly the asnwer of Igor Rivin: mathoverflow.net/questions/108726/… –  Lee Mosher Jul 5 '14 at 15:28
@Lee Such bounds are also mentioned in some MSE answers too. –  Bill Dubuque Jul 5 '14 at 16:08

Note that $$X^4 + X^3 + 2X^2 + X + 1 = [X^4 + X^3 + \underbrace{X^2] + [X^2}_{2X^2} + X + 1] = 0$$

$$\iff \color{blue}{X^2}(X^2+ X + 1) + \color{blue}{1}\cdot (X^2 + X + 1) = 0$$

$$\iff (X^2 + X + 1)(\color{blue}{X^2 + 1}) = 0$$

Now, each of these factors is irreducible in the reals, so cannot be factored further, meaning there are no real roots.

-
Thanx, I'm trying to write a program that will test if the polynomial can be factored, for me the output I got from wolfram is sufficient, But I can't seem to find a test that will tell me if a polynomial can be factored or not. –  Tamim Salem Jul 5 '14 at 15:14
That's a tall order, indeed. I approached this by "inspection" and I don't quite know how that can be translated into an algorithm! ;-) Wolfram seems to have come up with some approach, though I suspect, through computers, there may be a brute force approach, after failing, e.g. with the rational root theorem. –  amWhy Jul 5 '14 at 15:19
I know it is, but all I want is a mathematical test name, I'll do the reading and translation myself :) –  Tamim Salem Jul 5 '14 at 15:21
The fundamental theorem of algebra tells you every polynomial over $\mathbb{C}$ of degree $n$ has exactly $n$ roots counting multiplicity. –  Batman Jul 5 '14 at 15:36
@Tamim A more general method is to use undetermined coefficients, e.g. see my answer. If you want a general algorithm then that involves much more work, e.g. see prior answers here on polynomial factorization algorithms. –  Bill Dubuque Jul 5 '14 at 16:02

The method of undetermined coefficients works more generally than ad-hoc methods. Suppose it has a factorization into quadratics. By Gauss's Lemma we may assume their coef's $\,a_i,b_i\in\Bbb Z$

$$\begin{eqnarray} x^4+ x^3+ 2 x^2 + x + 1 &=& (x^2+a_1 x + a_0)\ (x^2+ b_1 x + b_0)\\ &=& x^4 + (a_1\!+\!b_1) x^3 + (a_1 b_1\! +\! a_0\! +\! b_0) x^2 + (a_0 b_1\! +\! a_1 b_0) x + a_0 b_0\end{eqnarray}$$

So $\ a_0b_0 = 1\,\Rightarrow\, a_0,b_0 = +1\,$ or $\,-1;\:$ it must be $+1$ else coef's of $\,x^3,\ x^1\,$ have opposite signs.

So specializing $\,a_0,b_0 = 1\,$ yields $\ x^4 + (\color{#0a0}{a_1\! + b_1}) x^3 + (\color{#c00}{a_1 b_1\! +2}) x^2 + (a_1\! +b_1) x + 1$

Therefore $\,\color{#c00}{a_1 b_1\! + 2} = 2\,\Rightarrow\, a_1 b_1 = 0,\,$ so $\,\color{#0a0}{a_1\! + b_1} = 1\,\Rightarrow\, a_1,b_1 = 0,1\,$ or $\,1,0.$

-

One way to do this sort of thing is to first factor it completely, into its complex factors, and then search for conjugate pairs among those factors. $X^4 + X^3 + 2X^2 + X + 1$ can be factored into $(X-\sqrt[3]{-1}+1) (X-i) (X+i) (X+\sqrt[3]{-1})$. A computer algorithm for finding real factors could then examine these complex factors, determine that $(X - i)$ and $(X + i)$ are conjugate pairs, and multiply them to produce a real factor, $(X^2+1)$. It could then do the same with $(X-\sqrt[3]{-1}+1)$ and $(X+\sqrt[3]{-1})$ to produce $(X^2 + X + 1)$.

-

Well you can always "cheat" and use complex numbers. Your polynomial has a root $x = i$, where $i^2 = -1$ ($i^3 = -i$, $i^4 = 1$).

$i^4 + i^3 + 2i^2 + i + 1 = 1 - i - 2 + i + 1 = 0$

$i$ is also a root of $p(x) = x^2 + 1$, because $i^2 + 1 = -1 + 1 = 0$. It's important that this works only because there is a polynomial $p(x)$ with real coefficients that has the same complex root as your initial polynomial. In fact, your polynomial has 3 more complex roots, but those wouldn't work. Read more in the fundamental theorem of algebra

-

Apart from just "seeing" the factorization as in the answer of amWhy, one can also use the fact that the polynomial is symmetric to reduce the degree of the problem. After dividing by $X^2$ one obtains a symmetric Laurent-polynomial \begin{align} X^2+X+2+X^{-1}+X^{-2}=(X+X^{-1})^2+(X+X^{-1})=Z^2+Z=Z\,(Z+1) \end{align} Here the resulting quadratic polynomial in $Z=X+X^{-1}$ has a trivial factorization, but any symmetric polynomial of degree 4 reduces in this way to a quadratic polynomial that can then be factorized into linear factors. Each linear factor $Z-a$ then gives a quadratic factor $X^2-aX+1$ of the original polynomial.

-