1
$\begingroup$

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

  • 2
    Keep going: $x^2=(x+1)(x+1)+1$2012-11-07
  • 0
    Hmm, right, I see. But in general how do I know when to stop, is it when I get to a 0 remainder?2012-11-07
  • 1
    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.2012-11-07
  • 0
    Ah of course.. thank you.2012-11-07
  • 0
    @Arvin / BK-201: If you found your solution, please post it as an answer to your question so that future readers can benefit from it.2012-11-07
  • 1
    But coordinators only do things that benefit themselves, Snowball :P just kidding - Answer posted! :)2012-11-07

1 Answers 1

1

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