Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

As wj32 stated, all I needed to do was to keep going one more step:


$(x+1)^2$ is $(x^2+2x+1)$ but of course $2x \equiv 0$ in $\mathbb Z_{2}$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.