<s>[INST] division of polynomials in $\mathbb{Z_2}$ I'm working on a problem involving division of polynomials in $\mathbb{Z_2}$. The question goes like this...
Find a greatest common divisor of the polynomials $x^6+x^4+x+1$ and $x^7+x^4+x^3+1$. 
My textbook gave some examples but skipped a lot of the work and cannot follow what is going on. One example from the book said to find a greatest common divisor of $x^4+x^3+x+1$ and $x^5+x^2+x+1$ in $\mathbb{Z_2}$
. They got...
$x^5+x^2+x+1$ = $(x+1)(x^4+x^3+x+1)+(x^3+x)...$ and similarly
$x^4+x^3+x+1 = (x+1)(x^3+x)+(x^2+1)$.
How did they get this result? This should help clear things a bit before attempting the problem.
EDIT
I've attempted the original book problem and my gcd came out to $x^3+1$.
 [/INST] I don't know how to typeset long division here, so I'll try to describe the procedure step-by-step instead. Say, we want to divide $x^5+x^2+x+1$ by $x^4+x^3+x+1$ with remainder over $\mathbb{Z}_2$. Dividing the leading terms gives us $x^5/x^4=\color{magenta}{x}$ as the first term of the quotient. Now,
$$\color{magenta}{x}\cdot(x^4+x^3+x+1)=x^5+x^4+x^2+x,$$
and
$$(x^5+x^2+x+1)-(x^5+x^4+x^2+x)=-x^4+1=x^4+1,$$
the last equality being true because we're in $\mathbb{Z}_2$ where $-1=1$. Now we continue in the same fashion to divide the current polynomial $x^4+1$ by $x^4+x^3+x+1$. Dividing the leading terms gives us $x^4/x^4=\color{magenta}{1}$ as the next term of the quotient. Then,
$$\color{magenta}{1}\cdot(x^4+x^3+x+1)=x^4+x^3+x+1,$$
and
$$(x^4+1)-(x^4+x^3+x+1)=-x^3-x=x^3+x,$$
for the same reason. So we ended up with the quotient of $\color{magenta}{x+1}$ and the remainder of $\color{blue}{x^3+x}$.
</s>