Die Polynomdivision
Sind f, g Polynome und ist c ∈ ℝ, so sind auch cf, f + g, f − g und fg Polynome. Im Allgemeinen können wir zwei Polynome aber nicht dividieren, ohne die Menge der Polynome zu verlassen. Gibt es ein Polynom q mit f = qg, so heißt g ein Teilerpolynom oder Teiler von f. Allgemein lässt sich eine Division mit Rest wie bei den ganzen Zahlen durchführen:
Satz (Polynomdivision mit Rest)
Seien f, g : ℝ → ℝ Polynome, und sei g nicht das Nullpolynom. Dann gibt es eindeutig bestimmte Polynome q und r mit
f = q g + r und deg(r) < deg(g).
Ist q ≠ 0, so ist der Grad von q die Differenz der Grade von f und g, da dann
deg(f) = deg(q g + r) = deg(q g) = deg(q) + deg(g)
Beweis
zur Existenz: Ist deg(f) < deg(g), so sind q = 0 und r = f wie gewünscht. Sei also deg(f) ≥ deg(g). Wir setzen f = f0. Wir werden Polynome qi und fi definieren mit
| f0 | = q1 g + f1, | deg(f1) < deg(f0), |
| f1 | = q2 g + f2, | deg(f2) < deg(f1), |
| … | ||
| fm − 1 | = qm g + fm, | deg(fm) < deg(g) ≤ deg(fm − 1). |
Dann gilt
f0 = q1 g + f1 = (q1 + q2) g + f2 = … = (q1 + … + qm) g + fm,
sodass die Summe der qi ein Polynom q und r = fm wie gewünscht sind.
Derartige Polynome qi und fi können wir aber rekursiv durch
(+) qi = ci xki, fi = fi − 1 − qi g,
definieren, wobei ci der Quotient der Leitkoeffizienten und ki die Differenz der Grade von fi − 1 und g ist.
zur Eindeutigkeit: Ist f = q g + r mit deg(r) < deg(g), so gilt (q − q) g = r − r und damit
deg(q − q) + deg(g) = deg(r − r) < deg(g).
Also ist q − q das Nullpolynom, sodass q = q und folglich r = r.
Wir nennen das Polynom q den Quotienten und das Polynom r den Rest der Division von f durch g.
Aus der Rekursion
(+) qi = ci xki, fi = fi − 1 − qi g,
gewinnen wir einen Algorithmus zur Durchführung der Polynomdivision. Das folgende Beispiel zeigt eine von vielen denkbaren Möglichkeiten, wie die Durchführung notiert werden kann.
Beispiel
f = x4 + 2x3 − 2x + 1, g = x2 + 1.
x4 | x3 | x2 | x1 | 1 | |
1 | 2 | 0 | −2 | 1 | f0 |
1 | 0 | 1 | 0 | 0 | x2 g |
2 | −1 | −2 | 1 | f1 | |
2 | 0 | 2 | 0 | 2x g | |
−1 | −4 | 1 | f2 | ||
−1 | 0 | −1 | −1 g | ||
−4 | 2 | f3 |
Ergebnis der Polynomdivision mit Rest von f durch g:
f = q g + r = (x2 + 2x − 1)g + (−4x + 2)
Zum Aufbau der Tabelle: Wir tragen in jeder Zeile die Koeffizienten des betrachteten Polynoms fi bzw. qi g ein. Dabei ist qi definiert durch ci xki wie in (+) und fi + 1 = fi − qi g die Differenz der beiden Vorgängerzeilen. Das Verfahren endet, sobald der Grad von fi kleiner als der Grad von g geworden ist. Der Quotient q ist die Summe der qi und der Rest r das letzte Differenzpolynom fm.
Der Nenner der Koeffizienten ci in qi = ci xki ist immer der Leitkoeffizient des Divisors g. Damit erhalten wir:
Satz (Erhalt ganzzahliger Koeffizienten)
Ist das Polynom g normiert und sind alle Koeffizienten des Polynoms f ganze Zahlen, so sind auch alle Koeffizienten des Quotienten und des Restes der Polynomdivision von f durch g ganze Zahlen.