de
Seitenbanner
Menu
Nachlesen

Division von Polynomen

Bei der Polynomdivision handelt es sich um eine Zerlegung mit Rest, die zu gegebenen Polynomen ein Quotienten- und ggf. ein Restpolynom liefert, das nicht als Vielfaches des Divisors dargestellt werden kann.

Definition

Gegeben seien zwei Polynome \(a(x)\) und \(b(x)\) mit Koeffizienten aus einem Ring mit Eins \(\mathcal{R}\). Falls es sich beim Leitkoeffizienten des Polynoms \(b(x)\) um eine Einheit des Rings \(\mathcal{R}\) handelt, also um ein Element mit einem multiplikativen Inversen, so existieren eindeutig bestimmte Polynome \(q(x)\) und \(r(x)\) mit \(\grad r(x) \lt \grad b(x)\), so dass gilt:

\[ a(x) = q(x) \cdot b(x) + r(x). \]

Hierbei handelt es sich um eine Zerlegung mit Rest von \(a(x)\) bezüglich \(b(x)\).

Beschreibung des Verfahrens

Seien \(a(x)\) und \(b(x)\) Polynome mit Koeffizienten aus einem Ring mit Eins \(\mathcal{R}\). Es gelte \(\grad a(x) = n\), \(\grad b(x) = m\) sowie \(\grad b(x) \leq \grad a(x)\).

Die Division von Polynomen funktioniert im Wesentlichen analog zur schriftlichen Division von ganzen Zahlen. Um das Polynom \(a(x)\) (den Dividenden) durch das Polynom \(b(x)\) (den Divisor) zu teilen, muss zunächst die höchste Potenz \(a_nx^n\) des Dividenden als Vielfaches der höchsten Potenz \(b_mx^m\) des Divisors dargestellt werden. Hierzu muss die Frage beantwortet werden, wie oft \(b_mx^m\) in \(a_nx^n\) hineinpasst bzw. womit \(b_mx^m\) multipliziert werden muss, um \(a_nx^n\) zu erhalten. Die erste Frage lässt sich direkt auf eine Division zurückführen:

\[ q_rx^r = \frac{a_nx^n}{b_mx^m} = \frac{a_n}{b_m}\, x^{n-m} \]

Da in vielen Ringen \(\mathcal{R}\) keine Division existiert – das gilt insbesondere, wenn es sich bei \(\mathcal{R}\) nicht um einen Körper handelt –, ist es meist sinnvoll, stattdessen die zweite Frage zu beantworten, nämlich womit \(b_mx^m\) multipliziert werden muss, um \(a_nx^n\) zu erhalten:

\begin{align*} a_n\,x^n &= (a_n \cdot 1)\,x^n \\[0.5em] &= \Bigl(a_n \cdot \left(b_m^{-1} \cdot b_m\right)\Bigr)\,x^{n} \\[0.5em] &= \Bigl(\left(a_n \cdot b_m^{-1}\right) \cdot b_m \Bigr)\,x^{(n-m)+m} \\[0.5em] &= \underbrace{\left(a_n \cdot b_m^{-1}\right)\,x^{n-m}}_{=\ q_rx^r} \cdot b_m\,x^m \end{align*}

Der Koeffizient \(q_r\) entspricht also dem Produkt \(a_nb_m^{-1}\), wobei \(b_m^{-1}\) das multiplikative Inverse des Leitkoeffizienten \(b_m\) des Divisors \(b(x)\) ist. Hierin liegt die Forderung begründet, dass es sich beim Leitkoeffizienten \(b_m\) des Divisors um eine Einheit des Rings \(\mathcal{R}\) handeln muss, da ansonsten das multiplikative Inverse \(b_m^{-1}\) nicht existiert. Da die Division, falls existent, im Allgemeinen als Verknüpfung mit dem multiplikativen Inversen definiert wird, entspricht der Quotient \(\frac{a_n}{b_m}\) dem Produkt \(a_nb_m^{-1}\).

Der so erhaltene Term \(q_rx^r\) wird als Summand in das Quotientenpolynom \(q(x)\) aufgenommen. (Anmerkung: Die kleineren Potenzen des Divisors \(b(x)\) können bei der Bestimmung von \(q_rx^r\) ignoriert werden, da bei der Multiplikation von Polynomen die höchste Potenz im Produkt ausschließlich durch das Produkt der höchsten Potenzen der Faktoren entsteht.)

Anschließend wird das \(q_rx^r\)-fache des Divisors \(b(x)\) vom Dividenden \(a(x)\) abgezogen; dies entspricht dem Teil des Dividenden, der nun als Vielfaches des Divisors dargestellt wurde. Bei der Differenz \(a(x)-q_rx^r \cdot b(x)\) handelt es sich folglich um den Rest des ursprünglichen Dividenden \(a(x)\), der noch nicht als Vielfaches des Divisors dargestellt wurde.

Für diesen Rest werden die beschriebenen Schritte nun erneut durchgeführt: Die höchste Potenz des Restpolynoms wird als Vielfaches der höchsten Potenz \(b_mx^m\) des Divisors dargestellt und das entsprechende Vielfache des Divisors vom Restpolynom abgezogen. Dies wird solange wiederholt, bis der Grad des Restpolynoms kleiner als der Grad des Divisors ist: Das Restpolynom kann dann nicht mehr als Vielfaches des Divisors dargestellt werden, womit die Abbruchbedingung des Algorithmus zur Polynomdivision erreicht ist.

Bei dem derart berechneten Polynom \(q(x)\) und dem verbleibenden Restpolynom \(r(x)\) handelt es sich um die eindeutig bestimmten Polynome der gesuchten Zerlegung mit Rest.

Beispiele

Beispiel 1

Gegeben seien die beiden nachfolgenden Polynome mit Koeffizienten aus den ganzen Zahlen \(\Z\):

\begin{align*} a(x) &= 3x^4 + 3x^2 + x + 1 \\[0.5em] b(x) &= x^2 - x + 3 \end{align*}

Für die Polynomdivision ergeben sich die folgenden Schritte:

\begin{align*} \begin{alignedat}{7} & & \llap{\bigl(} 3x^4 & & & \,+\, & 3x^2 & \,+\, & x & \,+\, & 1\rlap{\bigr)} & &\ \, : & \, \bigl({\color{Red}x^2} - x + 3\bigr) = {\color{CornflowerBlue} 3x^2} {\color{Orange}{}+ 3x} {\color{Magenta}{}-3} \\[0.5em] & \phantom{-\bigl(} & \llap{-\bigl(} {\color{CornflowerBlue}3x^4} & \,{\color{CornflowerBlue}-}\, & {\color{CornflowerBlue}3x^3} & \,{\color{CornflowerBlue}+}\, & {\color{CornflowerBlue}9x^2}\rlap{\bigr)} & & & & & & & \\[0.5em]\hline & & & & 3x^3 & \,-\, & 6x^2 & \,+\, & x & \,+\, & 1 & & & \\[0.5em] & & & & \llap{-\bigl(} {\color{Orange}3x^3} & \,{\color{Orange}-}\, & {\color{Orange}3x^2} & \,{\color{Orange}+}\, & {\color{Orange}9x}\rlap{\bigr)} & & & & & \\[0.5em]\hline & & & & & \,-\, & 3x^2 & \,-\, & 8x & \,+\, & 1 & & & \\[0.5em] & & & & & \llap{-\bigl(}\,{\color{Magenta}-}\, & {\color{Magenta}3x^2} & \,{\color{Magenta}+}\, & {\color{Magenta}3x} & \,{\color{Magenta}-}\, & {\color{Magenta}9}\rlap{\bigr)} & & & \\[0.5em]\hline & & & & & & & \,-\, & 11x & \,+\, & 10 & & & \end{alignedat} \end{align*}
  • Um das Polynom \(3x^4 + 3x^2 + x + 1\) als Vielfaches des Divisors \(x^2-x+3\) darzustellen, muss im ersten Schritt zunächst die höchste Potenz \(3x^4\) als Vielfaches von \({\color{Red}x^2}\) dargestellt werden; hierzu muss \({\color{Red}x^2}\) mit \({\color{CornflowerBlue} 3x^2}\) multipliziert werden. Folglich ist \({\color{CornflowerBlue} 3x^2}\) der erste Term des Quotienten. Um das verbleibende, noch darzustellende Restpolynom zu bestimmen, wird anschließend das \({\color{CornflowerBlue} 3x^2}\)-fache des Divisors, also \({\color{CornflowerBlue}3x^4-3x^2+9x^2}\), vom darzustellenden Polynom abgezogen.
  • Um das verbleibende Polynom \(3x^3-6x^2+x+1\) als Vielfaches des Divisors \(x^2-x+3\) darzustellen, muss im zweiten Schritt die höchste Potenz \(3x^3\) als Vielfaches von \({\color{Red}x^2}\) dargestellt werden; hierzu muss \({\color{Red}x^2}\) mit \({\color{Orange} 3x}\) multipliziert werden. Folglich ist \({\color{Orange} 3x}\) der zweite Summand des Quotienten. Um das verbleibende, noch darzustellende Restpolynom zu bestimmen, wird anschließend das \({\color{Orange} 3x}\)-fache des Divisors, also \({\color{Orange}3x^3-3x^2+9x}\), vom darzustellenden Polynom abgezogen.
  • Um das verbleibende Polynom \(-3x^2-8x+1\) als Vielfaches des Divisors \(x^2-x+3\) darzustellen, muss im dritten Schritt die höchste Potenz \(-3x^2\) als Vielfaches von \({\color{Red}x^2}\) dargestellt werden; hierzu muss \({\color{Red}x^2}\) mit \({\color{Magenta} -3}\) multipliziert werden. Folglich ist \({\color{Magenta} -3}\) der dritte Summand des Quotienten. Um das verbleibende, noch darzustellende Restpolynom zu bestimmen, wird anschließend das \({\color{Magenta}(-3)}\)-fache des Divisors, also \({\color{Magenta}-3x^2+3x-9}\), vom darzustellenden Polynom abgezogen.
  • Das verbleibende Polynom \(-11x+10\) kann nicht mehr als Vielfaches des Divisors \(x^2-x+3\) dargestellt werden, da der Grad \(1\) des Restpolynoms kleiner als der Grad \(2\) des Divisors ist.

Insgesamt ergibt sich die folgende Zerlegung mit Rest:

\[ \underbrace{3x^{4} + 3x^{2} + x + 1}_{=\ a(x)} = \Bigl(\underbrace{3x^{2} + 3x - 3}_{=\ q(x)}\Bigr) \cdot \Bigl(\underbrace{x^{2} - x + 3}_{=\ b(x)}\Bigr) + \Bigl(\underbrace{-11x + 10}_{=\ r(x)}\Bigr) \]

Beispiel 2

Gegeben seien die beiden nachfolgenden Polynome mit Koeffizienten aus dem Restklassenring \(\Z_5\):

\begin{align*} a(x) &= {[2]}_5x^3 + {[3]}_5x^2 + {[4]}_5x + {[1]}_5 \\[0.5em] b(x) &= {[3]}_5x^2 + {[1]}_5 \end{align*}

Für die Polynomdivision ergeben sich die folgenden Schritte:

\begin{align*} \begin{alignedat}{6} & & \llap{\bigl(} {[2]}_5x^3 & \,+\, & {[3]}_5x^2 & \,+\, & {[4]}_5x & \, + \, & {[1]}_5\rlap{\bigr)} & &\ \, : & \, \bigl({\color{Red}{[3]}_5x^2} + {[1]}_5\bigr) = {\color{CornflowerBlue}{[4]}_5x} {\color{Orange}{}+{[1]}_5}\\[0.5em] & \phantom{-\bigl(} & \llap{-\bigl(} {\color{CornflowerBlue}{[2]}_5x^3} & & & \,{\color{CornflowerBlue}+}\, & {\color{CornflowerBlue}{[4]}_5x}\rlap{\bigr)} & & & & & \\[0.5em]\hline & & & & {[3]}_5x^2 & & & \,+\, & {[1]}_5 & & & \\[0.5em] & & & & \llap{-\bigl(} {\color{Orange}{[3]}_5x^2} & & & \,{\color{Orange}+}\, & {\color{Orange}{[1]}_5}\rlap{\bigr)} & & & \\[0.5em]\hline & & & & & & & & {[0]}_5 & & & \end{alignedat} \end{align*}
  • Um das Polynom \({[2]}_5x^3 + {[3]}_5x^2 + {[4]}_5x + {[1]}_5\) als Vielfaches des Divisors \({[3]}_5x^2 + {[1]}_5\) darzustellen, muss im ersten Schritt zunächst die höchste Potenz \({[2]}_5x^3\) als Vielfaches von \({\color{Red}{[3]}_{5}x^2}\) dargestellt werden; hierzu muss \({\color{Red}{[3]}_{5}x^2}\) mit \({\color{CornflowerBlue} {[4]}_5x}\) multipliziert werden. Folglich ist \({\color{CornflowerBlue} {[4]}_5x}\) der erste Term des Quotienten. Um das verbleibende, noch darzustellende Restpolynom zu bestimmen, wird anschließend das \({\color{CornflowerBlue}{[4]}_5x}\)-fache des Divisors, also \({\color{CornflowerBlue}{[2]}_5x^3 + {[4]}_5x}\), vom darzustellenden Polynom abgezogen.
  • Um das verbleibende Polynom \({[3]}_5x^2 + {[1]}_5\) als Vielfaches des Divisors \({[3]}_5x^2 + {[1]}_5\) darzustellen, muss im zweiten Schritt die höchste Potenz \({[3]}_5x^2\) als Vielfaches von \({\color{Red}{[3]}_{5}x^2}\) dargestellt werden; hierzu muss \({\color{Red}{[3]}_{5}x^2}\) mit \({\color{Orange} {[1]}_5}\) multipliziert werden. Folglich ist \({\color{Orange} {[1]}_5}\) der zweite Summand des Quotienten. Um das verbleibende, noch darzustellende Restpolynom zu bestimmen, wird anschließend das \({\color{Orange} {[1]}_5}\)-fache des Divisors, also \({\color{Orange}{[3]}_5x^2 + {[1]}_5}\), vom darzustellenden Polynom abgezogen.
  • Das verbleibende Polynom \({[0]}_5\) bedeutet, dass die Polynomdivision beendet ist und ohne Rest möglich war.

Das Polynom \(a(x)\) ist ohne Rest durch \(b(x)\) teilbar. Insgesamt ergibt sich die folgende Zerlegung mit Rest:

\[ \underbrace{{[2]}_{5}x^{3} + {[3]}_{5}x^{2} + {[4]}_{5}x + {[1]}_{5}}_{=\ a(x)} = \Bigl(\underbrace{{[4]}_{5}x + {[1]}_{5}}_{=\ q(x)}\Bigr) \cdot \Bigl(\underbrace{{[3]}_{5}x^{2} + {[1]}_{5}}_{=\ b(x)}\Bigr) \]

Eigenschaften

Verknüpfung

Bei der Polynomdivision handelt es sich im Allgemeinen nicht um eine innere zweistellige Verknüpfung \(\mathcal{R}[x] \times \mathcal{R}[x] \rightarrow \mathcal{R}[x]\) auf Polynomen aus dem Polynomring \(\mathcal{R}[x]\), da es sich beim Ergebnis der Polynomdivision zumeist nicht um ein einzelnes, sondern um zwei Polynome aus \(\mathcal{R}[x]\) handelt – das Quotientenpolynom \(q(x)\) und das Restpolynom \(r(x)\).

Ist die Division von Polynomen mit Koeffizienten aus einem (speziellen) Ring \(\mathcal{R}\) stets ohne Rest möglich, so handelt es sich beim Polynomring \(\mathcal{R}[x]\) um einen Körper; bei der Polynomdivision handelt es sich dann um die Umkehrung der Polynommultiplikation.

Euklidischer Ring

Ist die Polynomdivision für beliebige Elemente des Polynomrings \(\mathcal{R}[x]\) immer möglich, so handelt es sich bei \(\mathcal{R}[x]\) um einen euklidischen Ring. Umgekehrt gilt: Handelt es sich bei \(\mathcal{R}[x]\) um einen euklidischen Ring, so ist die Polynomdivision für beliebige Elemente von \(\mathcal{R}[x]\) immer möglich.

Dies ist genau dann der Fall, wenn es sich bei \(\mathcal{R}\) um einen Körper handelt.

Assoziativität

Die Division von Polynomen \(a(x)\), \(b(x)\) und \(c(x)\) ist nicht assoziativ; im Allgemeinen gilt:

\[ \Bigl(a(x) : b(x) \Bigr) : c(x) \neq a(x) : \Bigl( b(x) : c(x) \Bigr) \]

Die Nichtassoziativität der Division von Polynomen kann leicht mithilfe eines Gegenbeispiels gezeigt werden. Gegeben seien die folgenden Polynome:

\begin{align*} a(x) &= x^8 \\[0.5em] b(x) &= x^4 \\[0.5em] c(x) &= x^2 \end{align*}

Für die Polynome \(a(x)\), \(b(x)\) und \(c(x)\) gilt

\begin{align*} \Bigl( a(x) : b(x) \Bigr) : c(x) &= \underbrace{\Bigl( x^8 : x^4 \Bigr)}_{=\ x^2} : x^2 \\[0.5em] &= 1 \\[1em] a(x) : \Bigl( b(x) : c(x) \Bigr) &= x^8 : \underbrace{\Bigl( x^4 : x^2 \Bigr)}_{=\ x^2} \\[0.5em] &= x^4, \end{align*}

woraus unmittelbar die Nichtassoziativität der Division von Polynomen folgt.

Hinweis: Die Verkettung der Division funktioniert nur dann, wenn alle Divisionen jeweils ohne Rest möglich sind; ansonsten ist sie undefiniert.

Kommutativität

Die Division von Polynomen \(a(x)\) und \(b(x)\) ist nicht kommutativ; im Allgemeinen gilt:

\[ a(x) : b(x) \neq b(x) : a(x) \]

Die Nichtkommutativität der Division von Polynomen kann leicht mithilfe eines Gegenbeispiels gezeigt werden. Gegeben seien die folgenden Polynome:

\begin{align*} a(x) &= x^4 \\[0.5em] b(x) &= x^2 \end{align*}

Für die Zerlegungen mit Rest gilt

\begin{align*} a(x) : b(x) \Rightarrow x^4 &= \underbrace{x^2}_{=\ q(x)} \cdot x^2 + \underbrace{0}_{=\ r(x)} \\[0.5em] b(x) : a(x) \Rightarrow x^2 &= \underbrace{0}_{=\ q(x)} \cdot x^4 + \underbrace{x^2}_{=\ r(x)}, \end{align*}

woraus unmittelbar die Nichtkommutativität der Division von Polynomen folgt.

Neutrales Element

Es existiert kein neutrales Element bezüglich der Division von Polynomen. Das konstante Polynom \(1\) ist rechts-, aber nicht linksneutral.

Inverses Element

Das inverse Element eines Polynoms \(a(x)\) bezüglich der Polynomdivision existiert im Allgemeinen nicht.