# Finding the $\gcd$ of $a(x)$ and $b(x)$ in field $\mathbb{F}$

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

• You didn't complete the (Euclidean) division - doing so yields a remainder of smaller degree than the divisor. – 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$$.
• 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? – Zachary Jan 25 at 17:55