I'm trying to find the $\gcd$ of $a(x) = x^4 + 2x^3+x^2+4x+2$ and $b(x)=x^2+3x+1$ over $\mathbb{F_5}$. I've already tried Euclid's algorithm:

$x^4 + 2x^3+x^2+4x+2 = x^2(x^2+3x+1) - x^3+4x+2$. Now I should express $b(x)$ in terms of the remainder $-x^3+4x+2$, but I'm not sure how to do this since $\deg(b(x)) < 3$. Did I do something incorrectly? How do I find the $\gcd$?

  • $\begingroup$ You didn't complete the (Euclidean) division - doing so yields a remainder of smaller degree than the divisor. $\endgroup$ – Bill Dubuque Jan 25 at 18:00

It is perhaps easier just to factorize the polynomials over $\Bbb F_5$ instead of using the Euclidean algorithm:

$$ x^4+2x^3+x^2+4x+2=(x^3+3x^2+4x+3)(x+4) $$

$$ x^2+3x+1=(x+4)^2 $$

For this is enough to look for roots. The second polynomial obviously has $x=-4=1$ as a double root. So what about the first polynomial? Clearly it has also a root $1$. What about the cubic polynomial left?

So you see that $gcd(a(x),b(x))=x+4$ over $\Bbb F_5$. Note that the gcd is $1$ over $\Bbb Z$.

  • $\begingroup$ Thanks! One more question: assume I want to find the coefficients $\lambda (x), \mu (x)$ such that $\gcd(a(x),b(x)) = \lambda (x) a(x) + \mu (x) b(x)$. Can I find them using your method? $\endgroup$ – Zachary Jan 25 at 17:55
  • 1
    $\begingroup$ @Zachary Use the Extended Euclidean algorithm, e.g. see here. $\endgroup$ – Bill Dubuque Jan 25 at 18:03

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.