Previously we indicated that the greatest common divisor (gcd) of a pair of two polynomials can be calculated with the Euclidean algorithm. Sometimes we are not only interested in the gcd, but also in the possibility of writing a greatest common divisor as a sum of multiples of #f# and #g#.
Let #f# and #g# be polynomials with #f\ne0# and #\deg(f)\ge \deg(g)#. Write #d# for a greatest common divisor of #f# and #g#. Then there are polynomials #a# of degree \(\deg(a)\le\deg(f)-\deg(d)\) and \(b\) of degree \(\deg(b)\le\deg(g)-\deg(d)\), such that
\[d = a\cdot f + b\cdot g\]
The algorithm below describes how to calculate a gcd of #f# and #g# together with the polynomials #a# and #b# as above. The sign #:=# indicates that the components of the vector on the left-hand side get new values that are prescribed by the right-hand side.
input: a pair #\rv{f,g}# of polynomials with #f\ne0# or #g\ne0#
output: a pair #\rv{a,b}# of polynomials with #a\cdot f+b\cdot g = \gcd\left(f,g\right)#
- Choose #Q = \matrix{1&0\\ 0 &1}# and #\matrix{r\\ s}= \matrix{f\\ g}#.
- Keep calculating the quotient #q# of division of #r# by #s# and renew the values \[\begin{array}{rcl} \small Q &:=&\small \matrix{0&1\\1&-q}\, Q\\ \matrix{r\\ s} &:=&\matrix{0&1\\1&-q}\matrix{r\\ s} \end{array}\] until #s=0#.
- Return #\rv{a,b} = \rv{Q_{11},Q_{12}}#.
Let #f=x^6-1# and #g=x^4-1#. In step 1 we get #r=x^6-1# and #s=x^4-1#. In step 2 division with remainder of #r# by #s# gives #t = x^2-1# (and quotient #q_1= x^2#), so the new values for #r# and #s# are #\rv{r,s} = \rv{x^4-1,x^2-1}#. We write #q_i# instead of #q# for the quotient in the #i#-th iteration in order to preserve the values of the quotients from different steps. Performing another division with remainder of #r# by #s# gives #t = 0# (and quotient # q_2 = x^2+1#), so the new values for #r# and #s# are #\rv{r,s} = \rv{x^2-1,0}#. Now the second component is equal to #0#, so that we get the first component in step 3: #\gcd(f,g) = x^2-1#.
The quotients #q_1# and #q_2# can be used to write #\gcd(f,g)# as a combination of the polynomials #f# and #g#:
\[\begin{array}{rcl}\matrix{\gcd(f,g)\\ 0} &=& \matrix{0& 1\\ 1&-q_2 }\,\matrix{0& 1\\1& -q_1 }\matrix{f\\ g}\\ &=& \matrix{0& 1\\1&-x^2-1 }\,\matrix{0& 1\\1&-x^2 }\matrix{f\\ g} \\ &=& \matrix{1& -x^2\\-x^2-1&x^4+x^2+1 }\,\matrix{f\\ g} \end{array}\]
The first row shows that #\gcd(f,g) = f-x^2\cdot g# and the second that #(x^2+1)\cdot f-(x^4+x^2+1)\cdot g =0#.
The calculation of #r# and #s# works in the same way as in the Euclidean algorithm. After each step we have \[\matrix{r\\ s} = Q\,\matrix{f\\ g}\]
This holds after the first step since #r=f# and #s=g#, and because #Q# is the identity matrix. In step 2 the dependency remains intact because both #\matrix{r\\ s}# and #Q# are multiplied by #\matrix{0&1\\ 1& -q}# from the left. In step 3 the values of #r#, #s#, and #Q# are not altered anymore. The conclusion is that at the end of the algorithm we have \(\matrix{d\\ 0} = Q\,\matrix{f\\ g}\). When comparing the vectors on the left- and right-hand side, we find #d=Q_{11}\cdot f+Q_{12}\cdot g#. Here, #d# is a gcd since #s=0#. Hence, the vector #\rv{a,b} =\rv{Q_{11},Q_{12}}# satisfies the requested equation.
We will also give a proof of the stated upper bounds on the degrees of polynomials appearing in the output. Let #f# and #g# be polynomials with #f\ne0# and #\deg(f)\ge \deg(g)#. Write #Q = \matrix{a&b\\ u&v}#. If # g=0#, then #a=1# and #b=0#, so both sides of the first inequality are equal to #0# and both sides of the second inequality are equal to #-1#. In particular, both inequalities hold.
Therefore, for the remainder of the proof, we (may and will) assume that #g\ne0#, which results in the fact that in step 2 at least one iteration takes place. The bounds on the degrees follow from the next set of inequalities, where, just as for #q_i# in the discussion of the Euclidean algorithm itself, the index #i\ge1# indicates the value of the polynomial at the end of the #i#-th iteration in step 2.
\[\begin{array}{rcl}
\deg(a_i)&\le&\deg(g)-\deg(r_i)\\
\deg(b_i)&\le&\deg(f)-\deg(r_i)\\
\deg(u_i)&\le&\deg(g)-\deg(r_i)\\
\deg(v_i)&\le&\deg(f)-\deg(r_i)\\
\deg(r_i)&\lt&\deg(s_{i-2})\phantom{xx}\text{ if }i\ge2\\
\deg(s_i)&\lt&\deg(r_i)\\
\end{array}\] The last inequality follows from the fact that #s_i# is the remainder when dividing #r_{i-1}# by #s_{i-1}#, so #\deg(s_i)\lt \deg(s_{i-1})=\deg(r_{i})#. The second-to-last inequality follows from the fact that #s_{i-1}# is the remainder when dividing #r_{i-2}# by #s_{i-2}#, so #\deg(r_i)=\deg(s_{i-1})\lt \deg(s_{i-2})#.
We will now concentrate on the proof of the first four inequalities. Note that #r_1=g#. The four inequalities all hold for #i=1#, where #q_1# is the quotient when dividing #f# by #g#:
\[\begin{array}{rcl}
\deg(a_1)&=&\deg(u_0)=\deg(0)=-1\lt 0=\deg(g)-\deg(r_1)\\
\deg(b_1)&=&\deg(v_0)=\deg(1)=0\le\deg(f)-\deg(r_1)\\
\deg(u_1)&=&\deg(a_0-q_1\cdot u_0)=\deg(1)=0=\deg(g)-\deg(r_1)\\
\deg(v_1)&=&\deg(b_0-q_1\cdot v_0)=\deg(q_1)=\deg(f)-\deg(r_1)
\end{array}\] We continue the proof with induction to #i#. Now assume that #i\ge 2# and that all four inequalities hold for smaller values of #i#.
\[\begin{array}{rcl}
\deg(a_i)&=&\deg(u_{i-1})\\
&&\phantom{xx}\color{blue}{\text{definition }a_{i}}\\
&\le&\deg(g)-\deg(r_{i-1})\\
&&\phantom{xx}\color{blue}{\text{induction hypothesis}}\\
&\le&\deg(g)-\deg(s_{i-2})\\
&&\phantom{xx}\color{blue}{\text{definition }r_{i-1}}\\
&\lt&\deg(g)-\deg(r_{i})\\
&&\phantom{xx}\color{blue}{\text{second-to-last inequality }}\\
\end{array}\]This establishes the first inequality. The proof of the second inequality works in the same way, but now with #b#, #v#, and #f# instead of #a#, #u#, and #g#.
Regarding the third inequality, we use the fact that the quotient #q_i# when dividing #r_{i-1}# by #s_{i-1}# has degree #\deg(r_{i-1})-\deg(s_{i-1})#:
\[\begin{array}{rcl}
\deg(u_i)&=&\deg(a_{i-1}-q_i\cdot u_{i-1})\\
&&\phantom{xx}\color{blue}{\text{definition }u_{i}}\\
&\le&\max\left(\deg(a_{i-1}),\deg(q_i\cdot u_{i-1})\right)\\
&&\phantom{xx}\color{blue}{\deg(p+q)\le \max(\deg(p),\deg(q))}\\
&\le&\max\left(\deg(g)-\deg(r_{i-1}),\right.\\
&&\phantom{xx}\left.\deg(r_{i-1})-\deg(s_{i-1})+\deg(g)-\deg(r_{i-1})\right)\\
&&\phantom{xx}\color{blue}{\text{induction hypothesis}}\\
&\le&\max\left(\deg(g)-\deg(r_{i-1}),\deg(g)-\deg(s_{i-1})\right)\\
&&\phantom{xx}\color{blue}{\text{expression simplified }}\\
&=&\max\left(\deg(g)-\deg(r_{i-1}),\deg(g)-\deg(r_{i})\right)\\
&&\phantom{xx}\color{blue}{\text{definition }r_{i}}\\
&=&\deg(g)-\deg(r_i)\\
&&\phantom{xx}\color{blue}{\deg(r_{i})=\deg(s_{i-1})\lt \deg(r_{i-1})}
\end{array}\] The proof of the fourth inequality corresponds with the proof of the previous inequality, but now with #b#, #v#, and #f# instead of #a#, #u#, and #g#.
After performing the algorithm, the polynomials #u# and #v# from the proof satisfy #u\cdot f + v\cdot g=0#. Moreover, each other pair #\rv{u_1,v_1}# that satisfies the equation #u_1\cdot f + v_1\cdot g = 0# is a multiple of #\rv{u,v}# in the sense that there exists a polynomial #w# such that #u_1=w\cdot u# and #v_1 = w\cdot v#.
Once we know the greatest common divisor #d# of #f# and #g#, we can find #a# and #b# by solving the system of linear equations \[\left(\sum_{i=0}^m a_ix^i\right)\cdot f +\left(\sum_{i=0}^n b_ix^i\right)\cdot g= d\] in the unknowns #a_0,a_1,\ldots,a_m,b_0,b_1,\ldots,b_n#, where #m =\deg(f)-\deg(d)# and #n = \deg(g)-\deg(d)#.
If #d# is unknown, then the left-hand side can also be used to look for a polynomial unequal to #0# of the form #a\cdot f+b\cdot g# of the smallest possible degree; in this case #m =\deg(f)# and #n = \deg(g)# can be chosen. If that polynomial is found, then it will be a gcd of #f# and #g#.
After all, if #d# is the unique monic gcd, and the degree of #a\cdot f+b\cdot g# is bigger than #\deg(d)#, then division with remainder of #a\cdot f+b\cdot g# by #d# will lead to a solution of degree smaller than #d#, which contradicts the assumption.
A different approach is to look for polynomials #d#, #a#, #b#, #u#, and #v# such that
\[\matrix{d\\0} = \matrix{a&b\\ u&v}\,\matrix{f\\ g} \phantom{xxx}\text{with}\phantom{xxx} a\cdot v-b\cdot u = \pm 1\]The solution found with the extended Euclidean algorithm satisfies all of these conditions since #Q# is the product of matrices of the form #\matrix{0&1\\ 1 & *}# all having determinant #-1#.
Then the matrix #\matrix{a&b\\ u&v}# is invertible with inverse #\pm\matrix{v&-b\\ -u&a}#, so
\[\matrix{f\\ g} = \pm\matrix{v&-b\\ -u&a}\,\matrix{d\\ 0} =\pm d\cdot \matrix{v\\ -u}\] This means that #d# is a divisor of #f# and of #g#, which is a combination (being #a\cdot f + b\cdot g#) of #f# and #g#. It follows that #d# is a gcd of #f# and #g#.
Calculate the greatest common divisor of \[\begin{array}{rcl}f(x)&=&x^3+5 x^2+9 x+6\\
&\text{and}&\\
g(x)&=&x^4+6 x^3+15 x^2+18 x+8\end{array}\] by using the
Euclidean algorithm.
#x+2#
By use of the
Euclidean algorithm we find
\[\begin{array}{rcl}\gcd(f(x),g(x))&=&{\small \gcd(x^3+5 x^2+9 x+6,x^4+6 x^3+15 x^2+18 x+8)}\\
&=&{\small \gcd(x^4+6 x^3+15 x^2+18 x+8,x^3+5 x^2+9 x+6)}\\
&&\phantom{xx}\color{blue}{\text{highest degree polynomial in first argument}}\\
&=& \gcd(x^3+5 x^2+9 x+6,x^2+3 x+2)\\
&&\phantom{xx}\color{blue}{\text{iteration 1: }x^2+3 x+2\text{ is the remainder}}\\
&&\phantom{xx}\color{blue}{\text{of division of }x^4+6 x^3+15 x^2+18 x+8}\\
&&\phantom{xx}\color{blue}{\text{by }x^3+5 x^2+9 x+6}\\
&=& \gcd(x^2+3 x+2,x+2)\\
&&\phantom{xx}\color{blue}{\text{iteration 2: } x+2\text{ is the remainder}}\\
&&\phantom{xx}\color{blue}{\text{of division of }x^3+5 x^2+9 x+6}\\
&&\phantom{xx}\color{blue}{\text{by }x^2+3 x+2}\\
&=&\gcd(x+2,0)\\
&&\phantom{xx}\color{blue}{\text{iteration 3: } 0 \text{ is the remainder}}\\
&&\phantom{xx}\color{blue}{\text{of division of }x^2+3 x+2}\\
&&\phantom{xx}\color{blue}{\text{by }x+2}\\
&=&x+2\\&&\phantom{xx}\color{blue}{\gcd(p(x),0)=p(x)}\end{array} \]