How can I calculate the greatest common divisor of two polynomials in a finite field?
I know it's through the Euclidean algorithm, but I don't know how to apply it to the finite fields case.
If I have $f(x)=x^4+3x^3+2x^2+4$ and $g(x)=x^2+3x+2$ in $\mathbb Z/5\mathbb Z$
How I could get $\gcd(f(x), g(x))$.
I have done this (Euclidean algorithm), but it doesn't coincide with your results:
https://screenshotscdn.firefoxusercontent.com/images/7abcb560-ec5b-453a-b71d-8b794548b267.png
Thanks a lot.
On
Just doing the division gives $f(x)=x^2g(x)+4$ and therefore any common divisor will be a factor of the remainder, $4$. That's essentially all Euclid's algorithm does, though it generally takes more steps than this.
Modulo $5$, we have that $4\equiv -1$ is a unit - the non-zero elements form a field. So the greatest common divisor is $1$. [Note that such divisors are only determined, in general, up to multiplication by a unit]
The Euclidean algorithm works over any field $K$, also over a finite field $\mathbb{F}_q$. Here we do not really need it, because $$ g(x)=(x+1)(x+2). $$ So all we need to test is, whether $x=-1$ or $x=-2$ is a root of $f(x)$. This is not the case, over $\mathbb{F}_5$, hence $$ \gcd(f,g)=1. $$