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.

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