# 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

-
Keep going: $x^2=(x+1)(x+1)+1$ –  wj32 Nov 7 '12 at 6:56
Hmm, right, I see. But in general how do I know when to stop, is it when I get to a 0 remainder? –  Arvin Nov 7 '12 at 7:03
Have you used the Euclidean algorithm for $\mathbb{Z}$ or $\mathbb{R}[x]$ before? It's exactly the same algorithm. You stop when you get 0. –  wj32 Nov 7 '12 at 7:03
Ah of course.. thank you. –  Arvin Nov 7 '12 at 7:04
But coordinators only do things that benefit themselves, Snowball :P just kidding - Answer posted! :) –  Arvin Nov 7 '12 at 8:21

$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}$