<s>[INST] Find monic gcd($x^4+x^3+x+1$, $x^6+x^5+x^4+x+1$) in $\mathbb Z_{2}$ My working so far using the Euclidean algorithm and polynomial long division (which I won't fully show here)
$x^6+x^5+x^4x+1$ = $(x^2+1) \times (x^4+x^3+x+1) + (-2x^3-x^2)$
and $(-2x^3-x^2) \equiv (x^2)$ in $\mathbb Z_{2}[x]$
So a non-monic gcd would be $x^2$? Should I keep going?
$x^4+x^3+x+1 = (x^2+x) \times (x^2) + (x+1)$
I'm a little confused now - when do I stop?
The answer is supposed to be 1 but I'm not seeing where 1 comes from
 [/INST] As wj32 stated, all I needed to do was to keep going one more step:
$x^2=(x+1)(x+1)+1$ 
$(x+1)^2$ is $(x^2+2x+1)$ but of course $2x \equiv 0$ in $\mathbb Z_{2}$ 
</s>