Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Express the greatest common divisor of the following pair of polynomials as a combination of polynomials: $f(x) = x^3 + x^2 +x +1$ and $g(x) = x^4 + x^2 + 1$.

I've been trying to understand this, but still can't get how I should do it in $\mathbb{Z}_2[x]$.

share|cite|improve this question
When dividing should I care about the coefficients or the exponents? – user40105 Sep 28 '12 at 4:11
The division algorithm is the same as always, except you perform coefficient arithmetic modulo $2$. For a convenient way to perform the extended Euclidean algorithm see here. – Bill Dubuque Sep 28 '12 at 4:19
So I used the Eucl. Algorithm with f(x)=x^3+x^2+x+1 and g(x)=x^4+x^2+1 as normally, and kept dividing until I got 3 in the remainder. So since 3 = 2 in Z2, I don't know what to do next. Stop dividing? – user40105 Sep 28 '12 at 4:32
$3=1$ in $\mathbb{Z}_2$. – Alexander Gruber Sep 28 '12 at 4:36
See the link I gave. You need to do the euclidean algorithm while simultaneously keeping track of each remainder as a linear combination of $f$ and $g$. – Bill Dubuque Sep 28 '12 at 4:36
up vote 1 down vote accepted

There’s really nothing different from solving such problems in $\Bbb Z$.

Using the Euclidean algorithm in its most straightforward form, not trying to be mechanically efficient:

$$\begin{align*} x^4+x^2+1&=(x+1)(x^3+x^2+x+1)+x^2\\ x^3+x^2+x+1&=(x+1)x^2+(x+1)\\ x^2&=x(x+1)+x\\ x+1&=1\cdot x+\color{red}{1} \end{align*}$$

The gcd is in red. Working upwards, and taking advantage of the fact that subtraction in $\Bbb Z_2[x]$ is addition, we have

$$\begin{align*} 1&=1\cdot(x+1)+1\cdot x\\ &=1\cdot(x+1)+1\cdot\left(x^2+x(x+1)\right)\\ &=(x+1)(x+1)+1\cdot x^2\\ &=(x+1)\left(f(x)+(x+1)x^2\right)+1\cdot x^2\\ &=(x+1)f(x)+\left((x+1)^2+1\right)x^2\\ &=(x+1)f(x)+x^2\cdot x^2\\ &=(x+1)f(x)+x^2\Big(g(x)+(x+1)f(x)\Big)\\ &=\left(x+1+x^2(x+1)\right)f(x)+x^2 g(x)\\ &=(x+1)\left(x^2+1\right)f(x)+x^2 g(x)\\ &=(x+1)^3 f(x)+x^2 g(x)\;. \end{align*}$$

As Bill Dubuque points out, and as is illustrated for numerical problems in the Wikipedia article on the extended Euclidean algorithm, there are more efficient ways to carry out the computations, but this is perhaps the easiest way to see clearly exactly what is going on.

share|cite|improve this answer

Your Answer


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