Finding GCD of two polynomials over a ring

Question

I'm trying to find the GCD of the two polynomials below over the ring GF(2)[x] and I'm having some trouble. The steps I did are below:

p(x) = x¹² + x⁹ + x⁸ + x⁶ + x⁴ + x + 1

q(x) = x¹¹ + x¹⁰ + x⁶ + x⁵ + x⁴ + x³ + 1

So, when I do p(x) / q(x) I get: x - 1 with a remainder of x¹⁰ + x⁹ + x⁸ - x⁷ + x⁶ + x⁴ + x³ + 2

I then take q(x) and divide by that remainder which gives me: x with a remainder of -x⁹ + x⁸ - x⁷ + x⁶ + x³ - 2x + 1

Then, I do (-x⁹ + x⁸ - x⁷ + x⁶ + x³ - 2x + 1) / (x¹⁰ + x⁹ + x⁸ - x⁷ + x⁶ + x⁴ + x³ + 2) = -x - 2 with a remainder of 2x⁸ - 2x⁷ + 3x⁶ + 2x⁴ + 3x³ - 2x² - 3x + 4

Now continuing this process gives me fractions which I know is not right, but I also know it isn't right that I have coefficients of 2 and greater when I divide by q(x) by the first remainder since it's over the ring GF(2). So what exactly am I doing wrong?

Answer 1

Another point of view is that over $\mathbb{F}_2$ both polynomials are reducible, and the Berlekamp factorisation algorithm quickly gives that \begin{align*} p(x) & = (x^7 + x^3 + x^2 + x + 1)(x^5 + x^2 + 1)\\ q(x) & = (x^6 + x^5 + x^3 + x^2 + 1)(x^5 + x^2 + 1), \end{align*} so that $gcd(p,q)=x^5+x^2+1$.