Eerder hebben we aangegeven dat een grootste gemene deler (ggd) van een tweetal veeltermen berekend kan worden met het algoritme van Euclides. Soms zijn we niet alleen geïnteresseerd in de ggd maar ook in de mogelijkheid een grootste gemeenschappelijke deler te schrijven als een som van een veelvoud van #f# en een veelvoud van #g#.
Laat #f# en #g# veeltermen zijn met #f\ne0# en #\deg(f)\ge \deg(g)#. Schrijf #d# voor een grootste gemene deler van #f# en #g#. Dan zijn er veeltermen #a# van graad \(\deg(a)\le\deg(f)-\deg(d)\) en \(b\) van graad \(\deg(b)\le\deg(g)-\deg(d)\), zodat
\[d = a\cdot f + b\cdot g\]
Onderstaand algoritme geeft aan hoe een ggd van #f# en #g# tezamen met de veeltermen #a# en #b# als hierboven berekend kan worden. Het teken #:=# geeft aan dat de componenten van de vector in het linker lid nieuwe waarden krijgen die voorgeschreven zijn door het rechter lid.
invoer: een paar #\rv{f,g}# van veeltermen met #f\ne0# of #g\ne0#
uitvoer: een paar #\rv{a,b}# van veeltermen met #a\cdot f+b\cdot g = \gcd\left(f,g\right)#
- Kies #Q = \matrix{1&0\\ 0 &1}# en #\matrix{r\\ s}= \matrix{f\\ g}#.
- Blijf het quotiënt #q# van deling van #r# door #s# berekenen en vernieuw daarbij de waarden\[\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}\] totdat #s=0#.
- Voer #\rv{a,b} = \rv{Q_{11},Q_{12}}# uit.
Laat #f=x^6-1# en #g=x^4-1#. In stap 1 wordt #r=x^6-1# en #s=x^4-1#. In stap 2 geeft deling van #r# door #s# met rest #t = x^2-1# (en quotiënt #q_1= x^2#) zodat de nieuwe waarden voor #r# en #s# zijn #\rv{r,s} = \rv{x^4-1,x^2-1}#. We schrijven #q_i# in plaats van #q# voor het quotiënt in de #i#-de iteratie van het algoritme om de waarden van de quotiënten in verschillende stappen vast te houden. Nogmaals deling van #r# door #s# met rest geeft #t = 0# (en quotiënt # q_2 = x^2+1#) zodat de nieuwe waarden voor #r# en #s# zijn #\rv{r,s} = \rv{x^2-1,0}#. Nu is de tweede component gelijk aan #0#, zodat in stap 3 de eerste component wordt afgeleverd: #\gcd(f,g) = x^2-1#.
De quotiënten #q_1# en #q_2# kunnen gebruikt worden om #\gcd(f,g)# als een combinatie van de veeltermen #f# en #g# te schrijven:
\[\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}\]
De eerste rij laat zien dat #\gcd(f,g) = f-x^2\cdot g# en de tweede dat #(x^2+1)\cdot f-(x^4+x^2+1)\cdot g =0#.
De berekening van #r# en #s# is dezelfde als in het algoritme van Euclides. Na elke stap geldt \[\matrix{r\\ s} = Q\,\matrix{f\\ g}\]
Na stap 1 geldt dit omdat #r=f# en #s=g#, en #Q# de identiteitsmatrix is. In stap 2 blijft de relatie behouden omdat zowel #\matrix{r\\ s}# als #Q# van links met #\matrix{0&1\\ 1& -q}# vermenigvuldigd worden. In stap 3 worden de waarden van #r#, #s# en #Q# niet meer veranderd. De conclusie is dat aan het einde van het algoritme geldt \(\matrix{d\\ 0} = Q\,\matrix{f\\ g}\). Vergelijken we de eerste component van de vectoren links en rechts, dan vinden we #d=Q_{11}\cdot f+Q_{12}\cdot g#. Hierbij is #d# een ggd omdat #s=0#. De vector #\rv{a,b} =\rv{Q_{11},Q_{12}}# voldoet dus aan de vereiste vergelijking.
We geven nog een bewijs van de genoemde bovengrenzen voor de graad van de veeltermen in de uitvoer. Laat #f# en #g# veeltermen zijn met #f\ne0# en #\deg(f)\ge \deg(g)#. Schrijf #Q = \matrix{a&b\\ u&v}#. Als # g=0#, dan is #a=1# en #b=0#, zodat beide zijden van de eerste ongelijkheid gelijk zijn aan #0# en beide zijden van de tweede ongelijkheid gelijk aan #-1#. In het bijzonder gelden beide ongelijkheden.
Daarom (mogen en) zullen we voor de rest van het bewijs aannemen dat #g\ne0#, wat erin resulteert dat in stap 2 ten minste één iteratie plaats vindt. De grenzen aan de graad volgen uit het volgende stel ongelijkheden, waarin, net als voor #q_i# in de bespreking van het algoritme van Euclides zelf, de index #i\ge1# de waarde van de veelterm aangeeft aan het einde van de #i#-de iteratie in stap 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{ als }i\ge2\\
\deg(s_i)&\lt&\deg(r_i)\\
\end{array}\] De laatste ongelijkheid volgt uit het feit dat #s_i# de rest is bij deling van #r_{i-1}# door #s_{i-1}#, zodat #\deg(s_i)\lt \deg(s_{i-1})=\deg(r_{i})#. De op een na laatste ongelijkheid volgt uit het feit dat #s_{i-1}# de rest is bij deling van #r_{i-2}# door #s_{i-2}#, zodat #\deg(r_i)=\deg(s_{i-1})\lt \deg(s_{i-2})#.
We concentreren ons nu op het bewijs van de eerste vier ongelijkheden. Merk op dat #r_1=g#. De ongelijkheden gelden alle vier voor #i=1#, waarbij #q_1# het quotiënt is bij deling van #f# door #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 vervolgen het bewijs met inductie naar #i#. Neem nu aan dat #i\ge 2# en stel dat alle vier ongelijkheden gelden voor kleinere waarden van #i#.
\[\begin{array}{rcl}
\deg(a_i)&=&\deg(u_{i-1})\\
&&\phantom{xx}\color{blue}{\text{definitie }a_{i}}\\
&\le&\deg(g)-\deg(r_{i-1})\\
&&\phantom{xx}\color{blue}{\text{inductiehypothese}}\\
&\le&\deg(g)-\deg(s_{i-2})\\
&&\phantom{xx}\color{blue}{\text{definitie }r_{i-1}}\\
&\lt&\deg(g)-\deg(r_{i})\\
&&\phantom{xx}\color{blue}{\text{een-na-laatste ongelijkheid}}\\
\end{array}\] Dit stelt de eerste gelijkheid vast. Het bewijs van de tweede ongelijkheid gaat net zo, maar dan met #b#, #v# en #f# in plaats van #a#, #u# en #g#.
Voor wat betreft de derde ongelijkheid gebruiken we het feit dat het quotiënt #q_i# bij deling van #r_{i-1}# door #s_{i-1}# graad #\deg(r_{i-1})-\deg(s_{i-1})# heeft:
\[\begin{array}{rcl}
\deg(u_i)&=&\deg(a_{i-1}-q_i\cdot u_{i-1})\\
&&\phantom{xx}\color{blue}{\text{definitie }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{inductiehypothese}}\\
&\le&\max\left(\deg(g)-\deg(r_{i-1}),\deg(g)-\deg(s_{i-1})\right)\\
&&\phantom{xx}\color{blue}{\text{uitdrukking vereenvoudigd}}\\
&=&\max\left(\deg(g)-\deg(r_{i-1}),\deg(g)-\deg(r_{i})\right)\\
&&\phantom{xx}\color{blue}{\text{definitie }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}\] Het bewijs van de vierde ongelijkheid komt overeen met het bewijs van de vorige ongelijkheid, maar dan met #b#, #v# en #f# in plaats van #a#, #u# en #g#.
De veeltermen #u# en #v# uit het bewijs voldoen na uitvoering van het algoritme aan #u\cdot f + v\cdot g=0#. Bovendien is elk ander paar #\rv{u_1,v_1}# dat voldoet aan de vergelijking #u_1\cdot f + v_1\cdot g = 0#, een veelvoud van #\rv{u,v}# in de zin dat er een veelterm #w# bestaat, zodat #u_1=w\cdot u # en #v_1 = w\cdot v#.
Als de grootste gemene deler #d# van #f# en #g# eenmaal bekend is, dan kunnen #a# en #b# ook worden gevonden door het lineaire stelsel vergelijkingen \[\left(\sum_{i=0}^m a_ix^i\right)\cdot f +\left(\sum_{i=0}^nb_ix^i\right)\cdot g= d\] in de onbekenden #a_0,a_1,\ldots,a_m,b_0,b_1,\ldots,b_n# op te lossen, waarbij #m =\deg(f)-\deg(d)# en #n = \deg(g)-\deg(d)#.
Als #d# niet bekend is, kan het linker lid ook gebruikt worden om te zoeken naar een veelterm ongelijk aan #0# van de vorm #a\cdot f+b\cdot g# van de kleinst mogelijke graad; hierbij kunnen #m =\deg(f)# en #n = \deg(g)# gekozen worden. Als die veelterm eenmaal gevonden is, dan zal deze een ggd van #f# en #g# zijn.
Immers, als #d# de unieke monische ggd is, en de graad van #a\cdot f+b\cdot g# is groter dan #\deg(d)#, dan leidt deling met rest van #a\cdot f+b\cdot g# door #d# tot een oplossing van graad kleiner dan #d#, in tegenspraak met de aanname.
Een andere benadering is om veeltermen #d#, #a#, #b#, #u# en #v# te vinden, zodat
\[\matrix{d\\0} = \matrix{a&b\\ u&v}\,\matrix{f\\ g} \phantom{xxx}\text{met}\phantom{xxx} a\cdot v-b\cdot u = \pm 1\] De via het uitgebreide algoritme van Euclides gevonden oplossing voldoet aan al deze voorwaarden omdat #Q# het product is van matrices van de vorm #\matrix{0&1\\ 1 & *}# die alle determinant #-1# hebben.
Dan is de matrix #\matrix{a&b\\ u&v}# namelijk inverteerbaar met inverse #\pm\matrix{v&-b\\ -u&a}#, zodat
\[\matrix{f\\ g} = \pm\matrix{v&-b\\ -u&a}\,\matrix{d\\ 0} =\pm d\cdot \matrix{v\\ -u}\] Dit betekent dat #d# een deler van #f# en van #g# is, die een combinatie is (namelijk #a\cdot f + b\cdot g#) van #f# en #g#. Hieruit volgt dat #d# een ggd van #f# en #g# is.
Bereken de grootste gemene deler van \[\begin{array}{rcl}f(x)&=&x^3+5 x^2+9 x+6\\
&\text{en}&\\
g(x)&=&x^4+6 x^3+15 x^2+19 x+10\end{array}\] met behulp van het
algoritme van Euclides.
#x+2#
Door toepassing van het
algoritme van Euclides vinden we
\[\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+19 x+10)}\\
&=&{\small \gcd(x^4+6 x^3+15 x^2+19 x+10,x^3+5 x^2+9 x+6)}\\
&&\phantom{xx}\color{blue}{\text{veelterm met hoogste graad voorop}}\\
&=& \gcd(x^3+5 x^2+9 x+6,x^2+4 x+4)\\
&&\phantom{xx}\color{blue}{\text{iteratie 1: }x^2+4 x+4\text{ is de rest}}\\
&&\phantom{xx}\color{blue}{\text{bij deling van }x^4+6 x^3+15 x^2+19 x+10}\\
&&\phantom{xx}\color{blue}{\text{door }x^3+5 x^2+9 x+6}\\
&=& \gcd(x^2+4 x+4,x+2)\\
&&\phantom{xx}\color{blue}{\text{iteratie 2: } x+2\text{ is de rest}}\\
&&\phantom{xx}\color{blue}{\text{bij deling van }x^3+5 x^2+9 x+6}\\
&&\phantom{xx}\color{blue}{\text{door }x^2+4 x+4}\\
&=&\gcd(x+2,0)\\
&&\phantom{xx}\color{blue}{\text{iteratie 3: } 0 \text{ is de rest}}\\
&&\phantom{xx}\color{blue}{\text{bij deling van }x^2+4 x+4}\\
&&\phantom{xx}\color{blue}{\text{door }x+2}\\
&=&x+2\\&&\phantom{xx}\color{blue}{\gcd(p(x),0)=p(x)}\end{array} \]
Het uitgebreide algoritme van Euclides
