2
$\begingroup$

How do we find the GCD $G$ of two polynomials, $P_1$ and $P_2$ in a given ring (for example $\mathbf{F}_5[x]$)? Then how do we find polynomials $a,b\in \mathbf{F}_5[x]$ so that $P_1a+ P_2b=G$? An example would be great.

2 Answers 2

3

If you have the factorization of each polynomial, then you know what the divisors look like, so you know what the common divisors look like, so you just pick out one of highest degree.

If you don't have the factorization, the Euclidean algorithm works for polynomials in ${\bf F}_5[x]$ just as it does in the integers, which answers the first question; so does the extended Euclidean algorithm, which answers the second question.

If you are unfamiliar with these algorithms, they are all over the web, and in pretty much every textbook that does field theory.

  • 0
    $x^2$ is not a divisor of $x^5-1$, and it's not a divisor of $2x^2+3x+1$, and either of those facts on its own would be enough to rule it out as the gcd. Do you know how gcds work in the integers? Can you see why 2 can't possibly be the gcd of 9 and 15? It's for roughly the same reason that $x^2$ can't be the gcd of your two polynomials.2011-11-28
2

The (extended) Euclidean algorithm works over any Euclidean domain, roughly, any domain enjoying a division algorithm producing "smaller" remainders, e.g. polynomial rings over fields, where the division algorithm yields smaller degree remainders (vs. smaller absolute value in $\mathbb Z$).