0
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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).$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How does this help with using Euclid's algorithm? $\endgroup$ – RghtHndSd May 14 '14 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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