Greatest Common Divisor of two binary polynomials

Question

How can I find the GCD of $x^4 + x^3 + x^2 + 1$ and $x^6 + x^5 + x^4 + x^3 + x^2 + 1$?

I know that $x^4 + x^3 + x^2 + 1$ is an irreducible polynomial of degree $4$, and that it is not primitive, but I don't know if that helps me in any way?

Answer 1

Use Euclid's algorithm in the usual way. The first step is $$(x^6+x^5+x^4+x^3+x^2+1)=(x^2)(x^4+x^3+x^2+1)+(x^3+1)$$ and the next will look like $$(x^4+x^3+x^2+1)=(\cdots)(x^3+1)+(\cdots)\ .$$