How to factor $x^5 + x + 1$?

I put $x^5 + x + 1$ into Wolfram and my TI-89 to factor it and they both arrived at the same factored answer:

$$(x^2+x+1)(x^3-x^2+1)$$

I've tried to expand this out to reverse engineer it:

\begin{aligned} (x^2+x+1)(x^3-x^2+1) &= x^2(x^3-x^2+1)+x(x^3-x^2+1) + 1(x^3-x^2+1) \\ &= x^5 \color{red}- \color{red}x^{\color{red}4} + \color{red}x^\color{red}2 + \color{red}x^\color{red}4 \color{red}-\color{red}x^\color{red}3 + x + \color{red}x^\color{red}3 \color{red}-\color{red}x^\color{red}2 + 1 \end{aligned}

I am not sure where one would even get the idea to both add and subtract those red terms into the original and then rearrange them in that way to factor it. Is there a thought process that would accompany this? Or is there another way to approach this question entirely?

• Yes, there is a way to approach this question with a little help from complex numbers. All you need to see is that a complex cube root of unity is a zero of the given polynomial, and then the factor $x^2+x+1$ comes out automatically. – астон вілла олоф мэллбэрг Feb 4 '18 at 9:39
• you can try this $$x^5+x+1=(x^2+ax+b)(x^3+cx^2+dx+e)$$ – Dr. Sonnhard Graubner Feb 4 '18 at 9:42
• Algebra's fundamentel theorem tells us that every real polynomial can be expressed as the product of quadratic and linear polynomials. Thus is natural to try to look for a factorization with a quadratic and a cubic polynomial. By doing some computations like @asdf's one, you get the answer – Caffeine Feb 4 '18 at 9:58
• Trick: any polynomial of the $x^{3k+2}+x+1$ form vanishes at the primitive third roots of unity, due to $\omega^2+\omega+1=0$, hence it is a multiple of $\Phi_3(x)=x^2+x+1$. – Jack D'Aurizio Feb 4 '18 at 17:52

A more intuitive way to factor it would be to add the terms $x^4 + x^3 +x^2$. Then the polynomial above will transform into:

$$x^5 + x^4 + x^3 +x^2 + x+1 - x^2(x^2 + x+ 1)$$ $$= \dfrac{x^6-1}{x-1} - x^2(x^2 + x+ 1)$$ $$= \dfrac{(x^3-1)(x^3+1)}{x-1} - x^2(x^2 + x+ 1)$$ $$= (x^2+x+1)(x^3+1)- x^2(x^2 + x+ 1)$$ Which gives the result.

There is a general method of factoring polynomials with rational coefficients, which is Kronecker's algorithm. However, I wouldn't apply it without trying first to reach a decomposition by trial and error.

Another general idea is the following:

Since your polynomial is of degree $5$ and $5=3+2=4+1$ then you get that you can factor it as either a linear polynomial times a polynomial of degree $4$ or a cubic times a quadratic. (Note: A linear polynomial is implied directly if you find a root).

If you try the $2+3=5$ you can do the following:

$$x^5+x+1=(ax^2+bx+c)(mx^3+nx^2+px+r)$$

for some real scalars. You can notice that after multiplying by some scalars and using the fact the $am=1$ you can assume $a=m=1$. Then you can expand the brackets on the right hand side and have a system of equations. If it has a solution - good, you've found a factorization. If not - you have to try the $1+4=5$. If you fail in that case, too then your polynomial is irreducible over the reals.

• Using the fundamental theorem of Algebra, we can easily show that every real polynomial can be factorized in the product of quadratic and linear polynomials. Thus it is not necessary to specify "if it has a solution", since it does – Caffeine Feb 4 '18 at 9:55
• It is still one of the best approaches in that it does not require so much intuition. – mathreadler Feb 4 '18 at 9:57

Factoring polynomials like this one is the famous blind deconvolution problem which pops up in all kinds of scientific and engineering applications. Therefore there have been researched very many numerical methods to try and calculate (huge) such factorizations. All of those algorithms you could also apply by hand on one dimensional polynomials if you want to (but it may be overkill for some of the most advanced of them).

So maybe not exactly 1 answer but it gives you the knowledge of what to search for to find 100s of methods.

At high school level: finding an obvious root. Note that the product of the complex roots is $-1$, so we may try to find roots with modulus $1$.

Let $\;j=\mathrm e^{\tfrac{2i\pi}3}$ and $\bar j=j^2$ the non-real cube root of $1$. This equation reminds us of the well-known relation: $$j^2+j+1=0,$$ and indeed, since $j^3=1$, $j^5=j^2$ so $j$ is a root. As the equation has real coefficients, its conjugate is also a root, so $x^5+x+1$ is divisible by $x-j$ and $x-j^2$, hence by their product $$(x-j)(x-j^2)=x^2+x+1.$$ There remains to perform the division.

• I wouldn't consider anything complex to be "high school level". Do high schoolers know complex numbers where you live? – Dylan Feb 4 '18 at 12:09
• @Dylan: Absolutely, in the last grade. – Bernard Feb 4 '18 at 13:37