Why does the Euclidean algorithm work for polynomials? What is the proof?

Solution 1:

The extended Euclidean GCD algorithm for polynomials over a field works the same way as it does for integers. Usually it is easiest to use the augmented-matrix form, e.g. from this answer, we compute the Bezout equation for $\gcd(f,g)\,$ over $\Bbb Q$.

$\!\begin{eqnarray} [\![1]\!]&& &&f = x^3\!+2x+1 &\!\!=&\, \left<\,\color{#c00}1,\ \ \ \ \color{#0a0}0\,\right>\quad {\rm i.e.}\ \qquad f\, =\ \color{#c00}1\cdot f\, +\, \color{#0a0}0\cdot g\\ [\![2]\!]&& &&\qquad\ \, g =x^2\!+1 &\!\!=&\, \left<\,\color{#c00}0,\ \ \ \ \color{#0a0}1\,\right>\quad{\rm i.e.}\ \qquad g\, =\ \color{#c00}0\cdot f\, +\, \color{#0a0}1\cdot g\\ [\![3]\!]&:=&[\![1]\!]-x[\![2]\!]\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\ \ x+1 \,&\!\!=&\, \left<\,\color{#c00}1,\,\color{#0a0}{-x}\,\right>\ \ \ \ {\rm i.e.}\quad x\!+\!1 =\: \color{#c00}1\cdot f\,\color{#0c0}{-\,x}\cdot g\\ [\![4]\!]&:=&[\![2]\!]+(1\!-\!x)[\![3]\!]\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\qquad\ 2 \,&\!\!=&\, \left<\,\color{#c00}{1\!-\!x},\,\color{#0a0}{1\!-\!x+x^2}\,\right>\\ \end{eqnarray}$

Hence the prior line implies: $\,\ \ 2\, =\, (\color{#c00}{1\!-\!x})f + (\color{#0a0}{1\!-\!x\!+\!x^2})g\ \ \ $ [Bezout equation]

Normalizing to a monic gcd: $\,\ \ \ 1\, =\, \dfrac{\color{#c00}{1\!-\!x}}{2}\,f \,+ \dfrac{\color{#0a0}{1\!-\!x\!+\!x^2}}2\,g\,\ $ by scaling above by $1/2$.

The proof is also the same as for integers - by descent using (euclidean) division with remainder. The set $I = fR[x]+gR[x]$ of polynomials of form $\, a f + b g $ is an ideal, i.e. is closed under addition and scaling, so it is closed under remainder = mod, since that is a composition of such operations: $f_i\bmod g_i = f_i - q\, g_i.\,$ So the least degree $0\neq d\in I$ divides every $h\in I$ (else $0\neq h\bmod d\in I\,$ has smaller degree than $d).\,$ So $\,f,g\in I\,\Rightarrow\, d\,$ is a common divisor of $\,f,g,\,$ necessary greatest by $\, c\mid f,g\,\Rightarrow\, c\mid d\!=\! a f + b g,\,$ so $\,\deg c\le \deg d.\,$ To force $d$ unique (over a field) usually the convention is to scale it to be monic (lead coef $=1),\,$ as we did above.

This algorithm is an efficient way to search the set $I$ for a polynomial $\,d\neq 0\,$ of minimal degree, while also keeping track of each element's representation as a linear combination of $\,f\,$ and $\,g.\,$ The proof shows further that $\,d\,$ is the gcd of all elements of $I$.

The same ideas work for any Euclidean domain (i.e. enjoying division with (smaller) remainder).

Remark $\ $ Generally, this method is easier to memorize and much less error-prone than the alternative "back-substitution" method.

This is a special-case of Hermite/Smith row/column reduction of matrices to triangular/diagonal normal form, using the division/Euclidean algorithm to reduce entries modulo pivots. Though one can understand this knowing only the analogous linear algebra elimination techniques, it will become clearer when one studies modules - which, informally, generalize vector spaces by allowing coefficients from rings vs. fields. In particular, these results are studied when one studies normal forms for finitely-generated modules over a PID, e.g. when one studies linear systems of equations with coefficients in the non-field! polynomial ring $\rm F[x],$ for $\rm F$ a field, as above.

Solution 2:

Just an example, showing where the fractions show up. I like doing the extended part, i.e. finding the Bezout expression, using the formalism of continued fractions. The magenta expressions are the "partial quotients"

$$ \left( 5 x^{4} + 4 x^{3} + 3 x^{2} + 2 x + 1 \right) $$

$$ \left( 2 x^{3} + 3 x^{2} + 4 x + 5 \right) $$

$$ \left( 5 x^{4} + 4 x^{3} + 3 x^{2} + 2 x + 1 \right) = \left( 2 x^{3} + 3 x^{2} + 4 x + 5 \right) \cdot \color{magenta}{ \left( \frac{ 10 x - 7 }{ 4 } \right) } + \left( \frac{ - 7 x^{2} - 14 x + 39 }{ 4 } \right) $$ $$ \left( 2 x^{3} + 3 x^{2} + 4 x + 5 \right) = \left( \frac{ - 7 x^{2} - 14 x + 39 }{ 4 } \right) \cdot \color{magenta}{ \left( \frac{ - 8 x + 4 }{ 7 } \right) } + \left( \frac{ 120 x - 4 }{ 7 } \right) $$ $$ \left( \frac{ - 7 x^{2} - 14 x + 39 }{ 4 } \right) = \left( \frac{ 120 x - 4 }{ 7 } \right) \cdot \color{magenta}{ \left( \frac{ - 1470 x - 2989 }{ 14400 } \right) } + \left( \frac{ 34673}{3600 } \right) $$ $$ \left( \frac{ 120 x - 4 }{ 7 } \right) = \left( \frac{ 34673}{3600 } \right) \cdot \color{magenta}{ \left( \frac{ 432000 x - 14400 }{ 242711 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( \frac{ 10 x - 7 }{ 4 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 10 x - 7 }{ 4 } \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( \frac{ - 8 x + 4 }{ 7 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ - 20 x^{2} + 24 x }{ 7 } \right) }{ \left( \frac{ - 8 x + 4 }{ 7 } \right) } $$ $$ \color{magenta}{ \left( \frac{ - 1470 x - 2989 }{ 14400 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 1050 x^{3} + 875 x^{2} + 6438 x - 6300 }{ 3600 } \right) }{ \left( \frac{ 420 x^{2} + 644 x + 3173 }{ 3600 } \right) } $$ $$ \color{magenta}{ \left( \frac{ 432000 x - 14400 }{ 242711 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 18000 x^{4} + 14400 x^{3} + 10800 x^{2} + 7200 x + 3600 }{ 34673 } \right) }{ \left( \frac{ 7200 x^{3} + 10800 x^{2} + 14400 x + 18000 }{ 34673 } \right) } $$ $$ \left( 5 x^{4} + 4 x^{3} + 3 x^{2} + 2 x + 1 \right) \left( \frac{ 420 x^{2} + 644 x + 3173 }{ 34673 } \right) - \left( 2 x^{3} + 3 x^{2} + 4 x + 5 \right) \left( \frac{ 1050 x^{3} + 875 x^{2} + 6438 x - 6300 }{ 34673 } \right) = \left( 1 \right) $$