Factor $x^5+x^4+1$ into irreducible polynomials in $Z_2$

Question

The answer paper says we can do it like this $(x^2+x+1)(x^3+x+1)$, but I dont know how they got that. Can you please write a step by step tutorial?:D Thank you! (Since $0$ and $1$ are not roots, I can’t even start to factorize)

Answer 1

If it can be factored, it is factored as the product of irreducible polynomials of degree $2$ and $3$ respectively since it has no roots. So we may try to see whether it is divisible by an irreducible quadratic polynomial, i.e. a quadratic polynomial with no root. Over $\mathbf Z_2$, the single quadratic irreducible polynomial is $x^2+x+1$, since the other quadratic polynomials are $$x^2+x=x(x+1)\quad\text{ and }\quad x^2+1=(x+1)^2.$$ It happens the quotient is $x^3+x+1$, and it is irreducible since it has no root either.

Answer 2

Hint: Let $f=x^5+x^4+1$. Then:

• $\gcd(f,x^2-x)$ is a possible factor of $f$ of degree at most $1$

• $\gcd(f,x^4-x)$ is a possible factor of $f$ of degree at most $2$

• $\gcd(f,x^8-x)$ is a possible factor of $f$ of degree at most $3$

• $\gcd(f,x^{32}-x)=f$ iff $f$ is irreducible mod $2$

All gcds can be easily found with the Euclidean algorithm.

Solution:

• $\gcd(f,x^2-x)=1$

• $\gcd(f,x^4-x)=x^2 + x + 1$

• $\gcd(f,x^8-x)=x^3 + x + 1$

• $f=(x^2 + x + 1)(x^3 + x + 1)$

The two factors are irreducible mod $2$ because they have no roots.