# 2007 iTest Problems/Problem TB2

## Problem

Factor completely over integer coefficients the polynomial $p(x)=x^8+x^5+x^4+x^3+x+1$. Demonstrate that your factorization is complete.

## Solution

Note that $p(x)=(x^5+x+1)+(x^8+x^4+x^3)$. If $x\neq 1$ and $x^3=1$, then $x^5+x+1=x^2+x+1=0$ and $x^8+x^4+x^3=x^2+x+1=0$. Therefore if $x\neq 1$ and $x^3=1$, then $p(x)=0$. Hence $x^2+x+1|p(x)$. Dividing through gives us

$p(x)=(x^2+x+1)(x^6-x^5+2x^3-x^2+1)$

Using the Rational Root Theorem on the second polynomial gives us that $\pm 1$ are possible roots. Only $-1$ is a possible root. Dividing through gives us

$p(x)=(x+1)(x^2+x+1)(x^5-2x^4+2x^3-x+1)$

Note that $x^5-2x^4+2x^3-x+1$ can be factored into the product of a cubic and a quadratic. Let the product be

$x^5-2x^4+2x^3-x+1=(x^2+ax+b)(x^3+cx^2+dx+e)$

We would want the coefficients to be integers, hence we shall only look for integer solutions. The following equations must then be satisfied:

• $be=1$
• $ae+bd=-1$
• $c+ad+e=0$
• $b+ac+d=2$
• $a+c=-2$

Since $b$ and $e$ are integers, $(b,e)$ is either $(1,1)$ or $(-1,-1)$. Testing the first one gives

• $a+d=-1$
• $c+ad=-1$
• $ac+d=1$
• $a+c=-2$

We must have that $(a+c)-(a+d)=c-d=-2--1=-1$ $(ac+d)-(c+ad)=a(c-d)-(c-d)=(a-1)(c-d)=1--1=2$. Therefore $a-1=-2$, or $a=-1$. Solving for $c$ and $d$ gives $(a,b,c,d,e)=(-1,1,-1,0,1)$. We don't need to test the other one.

Hence we have

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

For any of the factors of degree more than 1 to be factorable in the integers, they must have rational roots, since their degrees are less than 4. None of them have rational roots. Hence $p(x)$ is completely factored.

### Alternate Solution

We write $$p(x)=x^8+x^5+x^4+x^3+x+1=$$ $$x^5(x^3+1)+x^3(x+1)+(x+1)=$$ $$(x+1)(x^5(x^2-x+1) + (x^3+1))=$$ $$(x+1)(x^5(x^2-x+1)+(x+1)(x^2-x+1))=$$ $$(x+1)(x^2-x+1)(x^5+x+1)=$$ $$(x+1)(x^2-x+1)(x^2+x+1)(x^3-x^2+1)$$

The factorization of $x^5+x+1$ is trivial once we look at the exponents modulo $3$; since any root $\omega$ of $x^2+x+1$ satisfies $\omega^3=1$, it follows that $x^2+x+1 | x^5+x+1$ and the cubic factor comes as a result of polynomial division.

To prove that this is a complete factorization, it suffices to note that the factors of degree greater than $1$ have no rational roots (follows from the rational root theorem and some small cases).