De grootste gemene deler van twee veeltermen

Invariante deelruimten van lineaire afbeeldingen: Diagonaliseerbaarheid

De grootste gemene deler van twee veeltermen

Bij de behandeling van het begrip minimumveelterm hebben we deling met rest van veeltermen gebruikt. We hebben daar gezien dat veeltermen rekenkundige overeenkomsten met gehele getallen vertonen, waarbij de graad van een veelterm vergelijkbaar is met de absolute waarde van een geheel getal. Dit gaat ook op voor het begrip grootste gemene deler, dat we later zullen gebruiken om de Jordannormaalvorm, een unieke vorm van een vierkante matrix binnen zijn conjugatieklasse, te vinden.

Laat $f,g$ veeltermen in één variabele zijn. Een gemeenschappelijke deler van $f$ en $g$ is een veelterm die zowel $f$ als $g$ deelt.

Als $f$ en $g$ beide ongelijk aan de nulveelterm zijn, dan heet een gemeenschappelijke deler van grootst mogelijke graad een grootste gemene deler (ggd, in het Engels gcd, voor greatest common divisor).

Elke grootste gemene deler van $f$ en $g$ is dan een veelvoud van elke deler van $f$ en $g$ .

In het bijzonder zijn grootste gemene delers uniek op een scalair veelvoud ongelijk aan $0$ na. Elk tweetal veeltermen waarvan ten minste één ongelijk is aan $0$ , heeft dus een unieke monische ggd.

Met $\gcd(f,g)$ geven we de monische ggd van $f$ en $g$ aan.

De monische ggd van $x^4-1$ en $x^6-1$ is $x^2-1$ . Dit is als volgt in te zien:

$x^2-1$ is monisch want de coëfficiënt van $x^2$ is gelijk aan $1$
$x^4-1 = (x^2-1)\cdot (x^2+1)$ , dus $x^2-1$ deelt $x^4-1$
$x^6-1 = (x^2-1)\cdot (x^4+x^2+1)$ , dus $x^2-1$ deelt $x^6-1$
Als $d$ een deler is van $x^4-1$ en $x^6-1$ van graad groter dan $2$ , dan moet $x^2+1$ (een deler van $x^4-1$ van graad $2$ ) een factor gemeen hebben met $d$ , zodat $d(\ii)=0$ of $d(-\ii) = 0$ . Maar $\ii^6-1=-2$ en $(-\ii)^6-1=-2$ , dus $\ii$ en $-\ii$ zijn geen nulpunten van $x^6-1$ , dus $x^2+1$ is geen deler van $x^6-1$ , een tegenspraak.

Met onderstaande rekenregels wordt de berekening eenvoudiger en de procedure systematischer.

De volgende regels zijn nuttig voor de berekening van ggd's van veeltermen. Ze vertonen grote gelijkenis met de rekenregels voor de ggd van gehele getallen.

Rekenregels voor ggd van veeltermen

Laat $f$ en $g$ veeltermen zijn, waarbij ten minste één van de twee ongelijk is aan $0$ .

${\gcd}(f,g)={\gcd}(g,f)$ .
${\gcd}(0,g)=\frac{g}{c}$ waarin $c$ de leidende coëfficiënt van $g$ is.
$\gcd(f,g) = \gcd(g,r)$ , waarbij $r$ de rest is bij deling van $f$ door $g$ .
Als $m$ een gemeenschappelijke deler is van $f$ en $g$ met leidende coëfficiënt gelijk aan $1$ , dan geldt $\gcd( f, g) = m\cdot\gcd\left(\frac{f}{m},\frac{g}{m}\right)$ .

Regels $1$ en $2$ volgen direct uit de definitie van gcd.

Om regel 3, $\gcd(f,g) = \gcd(g,r)$ , waarbij $r$ de rest is bij deling van $f$ door $g$ , te bewijzen, schrijven we $c = \gcd(g,r)$ en leiden we af dat $c$ de gcd van $f$ en $g$ is. Omdat $c$ zelf een gcd is, is de leidende coëfficiënt ervan gelijk aan $1$ . Uit de definitie van $c$ volgt dat $c$ een deler is van $g$ . Als $q$ het quotiënt is bij deling met rest van $f$ door $g$ , dan geldt $f=q\cdot g+r$ . Aangezien $c$ zowel $r$ als $g$ deelt, laat dit zien dat $c$ ook $f$ deelt. We moeten nog aantonen dat $c$ een gemeenschappelijke deler van $f$ en $g$ van hoogst mogelijke graad is. Stel dat $d$ een gemeenschappelijke deler van $f$ en $g$ is. Dan deelt $d$ ook $f-q\cdot g=r$ , zodat $d$ een gemeenschappelijke deler van $g$ en $r$ is. Dit heeft tot gevolg dat $d$ een deler van $c$ is, en dus een graad heeft die niet groter dan de graad van $c$ is.

Om regel 4 te bewijzen, schrijven we $e = m\cdot\gcd\left(\frac{f}{m},\frac{g}{m}\right)$ . De leidende coëfficiënt van $e$ is gelijk aan $1$ . Verder is duidelijk dat $e$ een deler is van $f$ omdat $\gcd\left(\frac{f}{m},\frac{g}{m}\right)$ een deler is van $\frac{f}{m}$ , en, net zo, dat $e$ een deler is van $g$ . We moeten nog afleiden dat elke gemeenschappelijke deler van $f$ en $g$ een deler is van $e$ . Laat $h$ zo'n gemeenschappelijke deler zijn. Schrijf $p=\gcd(m,h)$ en $q=\frac{h}{p}$ . Dan zijn $p$ en $q$ veeltermen met $h=p\cdot q$ . Bovendien deelt $q$ zowel $\frac{f}{m}$ als $\frac{g}{m}$ ; het is dus een deler van $\gcd\left(\frac{f}{m},\frac{g}{m}\right)$ . Omdat $p$ een deler is van $m$ , heeft dit tot gevolg dat $h=p\cdot q$ een deler is van $e$ . Hiermee is het bewijs van regel 5 afgerond.

Wat is de monische ggd van de veeltermen $f(x)=x^4-1$ en $g(x)=x^4+5$ ?

$\gcd(f(x),g(x))=$ $1$

De ggd kan als volgt worden bepaald door toepassing van de Rekenregel voor ggd van veeltermen over het vervangen van een argument van de ggd door een rest:

$\begin{array}{rcl} \gcd (f(x),g(x))&=&{\rm gcd}(x^4-1,x^4+5)\\ &=& \gcd(x^4-1,6)\\ &&\phantom{xx}\color{blue}{\text{tweede argument vervangen door rest}}\\ &&\phantom{xx}\color{blue}{\text{bij deling van dit argument door het eerste argument}}\\ &=& \gcd(0,6)\\ &&\phantom{xx}\color{blue}{\text{eerste argument vervangen door rest}}\\ &&\phantom{xx}\color{blue}{\text{bij deling van dit argument door het tweede argument}}\\ &=& 1 \end{array}$

Nieuw voorbeeld