Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

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|improve this answer

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

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

Your Answer

 
discard

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.