So I have two polynomials in $\mathbb{F}_2[x]$ that I am trying to find the GCD of: $f(x)=x^6+x^5+x^4+x^3+x+1$ and $g(x)=x^5+x^3+x^2+x$.
So I start the algorithm:
$f(x)=g(x)(x+1)+x^3+1$
$g(x)=(x^3+1)(x^2+1)+x+1$
$x^3+1=(x+1)(?)+...?$
This is where I am having an issue. To break down my work more:
$g(x)(x+1)=x^6+x^4+x^3+x^2+x^5+x^3+x^2+x=x^6+x^5+x^4+x$ so we have a remainder of $x^3+1$.
For the next one, $(x^3+1)(x^2+1)=x^5+x^3+x^2+1$ so we have a remainder of $x+1$.
However, for the last one, we need to find $h(x),r(x)$ such that $x^3+1=(x+1)h(x)+r(x)$. As $\deg(x+1)\gt \deg(r(x))$ this means that $r(x)=0$ or $1$.
Looking at $(x+1)h(x)$, to get the 3rd degree term we need $h(x)$ to have an $x^2$. I cannot seem to be able to find an $h(x)$ $r(x)$ combination that meets these requirements. Help would be appreciated.
You want $(x+1)h(x)=x^3+1+r(x)$, where $\deg r(x)<1$. As you note, you see that $h(x)$ needs to be of the form $x^2+\dots$. But then you get an $x^2=1\cdot x^2$ term in $(x+1)h(x)=(x+1)(x^2+\dots)$ you need to cancel, so $h(x)$ needs to also have an $x$ term. You then have to cancel the $x=1\cdot x$ term in $(x+1)h(x)=(x+1)(x^2+x+\dots)$, so $h(x)$ needs to have a $1$ term. You now have $h(x)=x^2+x+1$, and $(x+1)h(x)=x^3+1$, so your remainder $r(x)$ is just $0$.