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

I have two polynomials: $f: x^3 + 2x^2 - 2x -1$ and $g: x^3 - 4x^2 + x + 2$. I have to do two things: find $gcd(f,g)$ and find polynomials $a,b$ such as: $gcd(f,g) = a \cdot f + b \cdot v$. I have guessed their greatest common divisor: $(x-1)$, but I did it by looking for roots of both polynomials, and now I am stuck. How do I find the greatest common divisor using the Euclid algorithm? I started with $f(x) = g(x) + 3(2x^2 - x - 1)$, but then things go nuts, and I can't use Bézout's identity to bring it all back to $gcd(f,g) = a \cdot f + b \cdot v$.

share|cite|improve this question

The Extended Euclidean Algorithm described here also works for polynomials over any field. For example, below is a computation of $\,\gcd(x^4+x+1,x^2+1)\,$ over $\,\Bbb F_2 = \,$ integers mod $2$.

$$\begin{array}{cccc} & x^4\!+x+1 & 1 & 0\\ & x^2\!+1 & 0 & 1\\ &x^2\!+x+1 & 1 & x^2\\ & x & 1 & x^2\!+1\\ & 1 & x & x^3\!+x+1\\ \end{array}$$

where each row $\ a\ \ b\ \ c\ $ means that $\ a = b(x^4\!+x+1) + c(x^2\!+1).\ $ Hence, by the final row

$$ 1\, =\, x(x^4\!+x+1) + (x^3\!+x+1)(x^2\!+1)$$

which, finally, implies that $\ (x^3\!+x+1)(x^2\!+1) = 1\,$ in $\,\Bbb F_2[x]/(x^4\!+x+1).$

share|cite|improve this answer

Hints: $$x³+2x²-2x-1= (x-1)(3x+x²+1)$$ and $$ x³-4x²+x+2= (x-1)(-3x+x²-2) $$

share|cite|improve this answer
How does this help with using Euclid's algorithm? – RghtHndSd May 14 '14 at 19:40

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.