The Extended Euclidean Algorithm for Polynomials

The Polynomial Euclidean Algorithm computes the greatest common divisor of two polynomials by performing repeated divisions with remainder. The algorithm is based on the following observation: If $a=bq+r$, then $\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)$. Each time a division is performed with remainder, an old argument can be exchanged for a smaller (= lower degree) new one (i.e. swap out $a$ for $r$). Since our remainders are getting smaller and smaller (in degree), eventually one of them has to be $0$. At this point, $\mathrm{gcd}(r,0)=r$ and so the last nonzero remainder is the $\mathrm{gcd}(a,b)$.

Expressing the greatest common divisor of $a$ and $b$ as a polynomial linear combination of $a$ and $b$ is quite useful in a host of applications. Such a linear combination can be found by reversing the steps of the Euclidean Algorithm. Running the Euclidean Algorithm and then reversing the steps to find a polynomial linear combination is called the "extended Euclidean Algorithm".

Notice the selection box at the bottom of the Sage cell. By default, work is performed in the ring of polynomials with rational coefficients (the field of rational numbers is denoted by $\mathbb{Q}$). To work with integer coefficient modulo $n$ (i.e. $\mathbb{Z}_n$), you may select Zn and then pick a modulus $n$. Keep in mind that if $n$ isn't a (positive) prime number, the algorithm might fail.

The computation above is powered by SageMath. The Sage code is embedded in this webpage's html file. To view the code instruct your browser to show you this page's source. For example, in Chrome, right-click and choose "View page source".

Wikipedia entry for the Euclidean Algorithm and the Extended Euclidean Algorithm.