Net als bij gehele getallen bestaat er een algoritme van Euclides waarmee de gcd van twee veeltermen gevonden kan worden. Regels 1 en 2 voor de gcd van veeltermen zijn voldoende om de gcd te berekenen, zoals onderstaand algoritme laat zien.
Een algoritme is een stel stappen die achter elkaar uitgevoerd moeten worden om van een bepaald type gegevens een bepaald voorgeschreven resultaat te bereiken. Bij de presentatie van een algoritme, beginnen we te specificeren met welke gegevens het algoritme begint, de invoer, en wat het algoritme oplevert, de uitvoer. Vervolgens geven we de stappen aan waar het algoritme uit bestaat.
Onderstaand algoritme, genaamd het algoritme van Euclides voor veeltermen, berekent de ggd van twee veeltermen als ten minste één van de twee ongelijk is aan #0#.
invoer: een paar #\rv{f,g}# van veeltermen met #f\ne0# of #g\ne0#
uitvoer: #\gcd\left(f,g\right)#
- kies #\rv{r,s}= \rv{f,g}#
- blijf #\rv{r,s}# vervangen door #\rv{s,t}# totdat #s=0#, waarbij #t# de rest is bij deling van #r# door #s#,
- voer #r# 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 #x^2#) zodat de nieuwe waarden voor #r# en #s# zijn #\rv{r,s} = \rv{x^4-1,x^2-1}#. Nogmaals deling van #r# door #s# met rest geeft #t = 0# (en quotiënt # 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#.
Elke instantie van het paar #\rv{r,s}# in stap 2 voldoet aan #\gcd(r,s)=\gcd(f,g)#:
1. vanwege de definitie;
2. aan het einde van elke iteratie in stap 2 vanwege gcd-regel 3.
Als we klaar zijn met stap 2, dan geldt #s=0# en volgt #\gcd(f,g)=\gcd(r,0)=r#. De uitvoer is dus inderdaad #\gcd(f,g)#.
Omdat bij elke iteratie in stap 2 de graad van #r# strikt kleiner wordt, doorloopt het algoritme niet meer iteraties dan het maximum van de graden van #f# en #g#.
Als we de vectoren schrijven als kolommen, dan zegt stap 2 in termen van matrices
\[\matrix{r\\ s} \phantom{xx}\text{wordt vervangen door }\phantom{xx} \matrix{0&1\\ 1&-q}\matrix{r\\ s}\]waarbij #q# het quotiënt bij deling van #r# door #s# is.
Als stap 2 dus #m# keer doorlopen wordt voordat #s=0#, dan levert dit op
\[\matrix{\gcd(f,g)\\ 0} =\matrix{0&1\\ 1&-q_m}\cdots \matrix{0&1\\ 1&-q_1}\matrix{f\\ g}\]
voor veeltermen #q_1,\ldots,q_m#.
Het eerste element van de kolomvector rechts levert een combinatie van de vorm #a\cdot f + b\cdot g#, waarbij #a# en #b# veeltermen zijn, die gelijk is aan de berekende ggd. Het tweede element levert een combinatie #u\cdot f + v\cdot g#, waarbij #u# en #v# veeltermen zijn, die gelijk is aan #0#. We gaan hier later op in.
Een bijzondere toepassing van het algoritme van Euclides is de volgende eenvoudige bepaling van het bestaan van meervoudige wortels van veeltermen:
Laat #f# een veelterm zijn. Dan geldt #\gcd(f,f') = 1# dan en slechts dan als #f# geen meervoudige complexe wortels heeft.
Stel dat #a# een complexe meervoudige wortel van #f# is. Dan is er een veelterm #g# met #f = g\cdot (x-a)^2#. Dit heeft vanwege de productregel voor differentiëren tot gevolg dat \[f' = g'\cdot (x-a)^2+2 g\cdot(x-a) = (x-a)\left(g'\cdot (x-a)+2 g\right)\]In het bijzonder is #x-a# een deler van #f'#, zodat #x-a# een deler is van #\gcd(f,f')# en dus #\gcd(f,f')\ne1#.
Stel dat #a# een complexe enkelvoudige wortel van #f# is. Dan is er een veelterm #g# met #f = g\cdot (x-a)# en #g(a)\ne0#. Dan geeft de productregel voor differentiëren #f' = g'\cdot (x-a) + g#, zodat #f'(a) = g(a)\ne0#. Dus als #a# een enkelvoudige wortel van #f# is, dan geldt #f'(a)\ne0#. In het bijzonder is #x-a# geen deler van #f'# en dus ook geen deler van #\gcd(f,f')#. We concluderen dat als #f# geen complexe meervoudige wortels heeft, geen enkele lineaire factor van #f# een deler van #f'# is, zodat #\gcd(f,f')=1#.
Het bestaan van meervoudige wortels van een veelterm kun je met dit algoritme eenvoudig aantonen. Het vinden van zo'n wortel is daarmee nog niet zo eenvoudig. Het is gemakkelijker geworden omdat zo'n wortel ook een wortel is van de veelterm #d = \gcd(f,f')#, die veelal van lagere graad is dan #f#. Maar ook voor #d# kan het nog lastig zijn om een wortel te bepalen.
Bovenstaand criterium geeft een snelle methode om na te gaan of een vierkante matrix diagonaliseerbaar is:
Een vierkante matrix #A# is dan en slechts dan diagonaliseerbaar als de minimumveelterm #m_A# voldoet aan #\gcd(m_A,m_A') = 1#, waarbij #m_A'# de afgeleide van #m_A# is.
Volgens dit resultaat is een #(2\times2)#-matrix #A# is precies dan niet diagonaliseerbaar als de minimumveelterm het kwadraat van een lineaire veelterm #x-\lambda# is. In het bijzonder is de karakteristieke veelterm dan #(x-\lambda)^2#, zodat \[x^2-2\lambda\cdot x +\lambda^2 = p_A(x) = x^2-\text{trace}(A)\cdot x+\det(A)\] Vergelijking van de coëfficiënten van #x# en van de constanten aan beide zijden geeft \[\eqs{2\lambda &=& \text{trace}(A)\\ \lambda^2 &=& \det(A)}\]Eliminatie van #\lambda# geeft dat de karakteristieke veelterm van #A# precies dan een kwadraat is als \[\left(\text{trace}(A)\right)^2 - 4 \det(A)=0\]In dat geval is de unieke eigenwaarde #\lambda=\frac{\text{trace}(A)}{2}#. We zien dus dat #A# dan en slechts dan niet diagonaliseerbaar is als de minimumveelterm en de karakteristieke veelterm van #A# beide gelijk zijn aan \[\left(x -\frac{\text{trace}(A)}{2}\right)^2\] Een concreet voorbeeld is de matrix \( A = \matrix{1&a\\ 0&1}\). Hier is #\lambda = 1#, is de karakteristieke veelterm gelijk aan #(x-1)^2# en is de minimumveelterm dan en slechts dan gelijk aan #(x-1)^2# als #a\ne0#. De matrix #A# is dus alleen diagonaliseerbaar als #a=0#.
Bereken de grootste gemene deler van \[\begin{array}{rcl}f(x)&=&x^3+6 x^2+10 x+8\\
&\text{en}&\\
g(x)&=&x^4+9 x^3+29 x^2+43 x+28\end{array}\] met behulp van het
algoritme van Euclides.
#x+4#
Door toepassing van het
algoritme van Euclides vinden we
\[\begin{array}{rcl}\gcd(f(x),g(x))&=&{\small \gcd(x^3+6 x^2+10 x+8,x^4+9 x^3+29 x^2+43 x+28)}\\
&=&{\small \gcd(x^4+9 x^3+29 x^2+43 x+28,x^3+6 x^2+10 x+8)}\\
&&\phantom{xx}\color{blue}{\text{veelterm met hoogste graad voorop}}\\
&=& \gcd(x^3+6 x^2+10 x+8,x^2+5 x+4)\\
&&\phantom{xx}\color{blue}{\text{iteratie 1: }x^2+5 x+4\text{ is de rest}}\\
&&\phantom{xx}\color{blue}{\text{bij deling van }x^4+9 x^3+29 x^2+43 x+28}\\
&&\phantom{xx}\color{blue}{\text{door }x^3+6 x^2+10 x+8}\\
&=& \gcd(x^2+5 x+4,x+4)\\
&&\phantom{xx}\color{blue}{\text{iteratie 2: } x+4\text{ is de rest}}\\
&&\phantom{xx}\color{blue}{\text{bij deling van }x^3+6 x^2+10 x+8}\\
&&\phantom{xx}\color{blue}{\text{door }x^2+5 x+4}\\
&=&\gcd(x+4,0)\\
&&\phantom{xx}\color{blue}{\text{iteratie 3: } 0 \text{ is de rest}}\\
&&\phantom{xx}\color{blue}{\text{bij deling van }x^2+5 x+4}\\
&&\phantom{xx}\color{blue}{\text{door }x+4}\\
&=&x+4\\&&\phantom{xx}\color{blue}{\gcd(p(x),0)=p(x)}\end{array} \]