# How to find the GCD of two polynomials

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.

-

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.

-
So if we are given something like $x^5-1$ which is irreducible and $2x^2+3x+1$ which can be factored into $(2x+1)(x+1)$, then our GCD is simply $x$? –  johnnymath Nov 28 '11 at 5:29
$x^5-1$ is certainly not irreducible. And $x$ isn't a divisor of either of the two polynomials you mention, so it is certainly not the gcd. –  Gerry Myerson Nov 28 '11 at 6:22
I'm sorry, I made a mistake. So if $x^5-1$ is factored into $(x-1)(x^4+x^3+x^2+x+1)$ does this mean that our common divisor is $x^2?$ –  johnnymath Nov 28 '11 at 6:27
$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. –  Gerry Myerson Nov 28 '11 at 11:40

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

-