# Polynomdivision

Die Polynomdivision, auch Partialdivision genannt, ist ein mathematisches Rechenverfahren, bei dem ein Polynom durch ein anderes dividiert wird. Das Ergebnis ist ein „Ganzteil“-Polynom und evtl. ein Restpolynom. Das Verfahren verläuft analog zur üblichen und in der Schule gelehrten Division von Zahlen mit Rest. Während dort vorübergehend kleinere Dezimalstellen ignoriert werden und die nächste Ziffer des Ergebnisses ggf. erraten wird, ist hier der nächste Koeffizient durch Division der verbliebenen höchsten Koeffizienten exakt bestimmt.

## Allgemein
### Informell

Im Folgenden seien $n$ und $m$ natürliche Zahlen einschließlich Null ($n,m\in \mathbb {N} _{0}$) und der Einfachheit halber die Größen $a_{i}\ (0\leq i\leq n)$ und $b_{j}\ (0\leq j\leq m)$ stets ganze Zahlen, also Elemente von $\mathbb {Z}$. Hat man nun zwei Polynome, etwa
    $p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}\quad {\text{mit}}\ a_{n}\neq 0$
und
    $q(x)=b_{m}x^{m}+b_{m-1}x^{m-1}+\cdots +b_{2}x^{2}+b_{1}x+b_{0}\quad {\text{mit}}\ b_{m}\neq 0,$
so kann man sie unter gewissen formalen Voraussetzungen ähnlich wie ganze Zahlen durcheinander dividieren, also die Rechenaufgabe
    $p(x):q(x)=\;?$
lösen. Im Ergebnis finden sich dann zwei Polynome: Ein Polynom $s(x)$, das dem Ganzzahlquotienten in der Zahlendivision mit Rest entspricht, und ein Polynom $r(x)$, das sich nicht mehr weiter durch $q(x)$ teilen lässt und das dem Rest in der Zahlendivision entspricht:
    $p(x)=q(x)s(x)+r(x)$
oder in Analogie zur Schulschreibweise
    $p(x):q(x)=s(x){\text{ Rest }}r(x).$
Das Verfahren zum Auffinden dieser Lösung, bestehend aus $s(x)$ und $r(x)$, ist die Polynomdivision.
Dass sich hiernach $r(x)$ nicht weiter durch $q(x)$ teilen lässt, ist gleichbedeutend damit, dass der Polynomgrad von $r(x)$ kleiner ist als der von $q(x)$, weshalb dies in der formalen Definition der Rechenvorschrift (Algorithmus) auch als Abbruchbedingung gefordert wird. In der Zahlendivision mit Rest wird stattdessen gefordert, dass der Rest kleiner als der Divisor ist. Beide Nebenbedingungen sorgen im jeweiligen Verfahren dafür, dass der Rest eindeutig bestimmt ist.
Bei der formalen Definition des Verfahrens werden einige zusätzliche Bedingungen beachtet. Das kommt daher, dass man Polynome im Allgemeinen viel weitläufiger definieren kann, als es hier zur einfacheren Erklärung geschehen ist oder man es zum Beispiel aus der Schule kennt. Die Koeffizienten eines Polynoms etwa können dann aus beliebigen Ringen stammen. Dann dürfen aber wiederum die Koeffizienten der beiden Polynome nicht aus verschiedenen Ringen stammen. Daher definiert man, dass die Polynome in einem gemeinsamen Polynomring liegen müssen. Auch reicht es nicht mehr zu fordern, dass der „höchste“ Koeffizient (Leitkoeffizient) $b_{m}$ von $q(x)$ nur ungleich Null sein müsse. Vielmehr muss man fordern, dass er zudem eine Einheit des Ringes sein muss. Oder es wird das unten beschriebene Verfahren der Pseudo-Division angewendet.

### Formal

Bei der Polynomdivision sind zwei Polynome $p(x)$ und $q(x)$ eines Polynomringes $R[x]$ gegeben, wobei $R$ ein kommutativer Ring mit $1\neq 0$ und der Leitkoeffizient von $q(x)$ eine Einheit in $R$ ist, und es wird die Gleichung
    $p(x)=s(x)q(x)+r(x),$
nach den gesuchten Polynomen $s(x)$ und $r(x)$ gelöst, und zwar so, dass der Grad von $r(x)$ kleiner als der von $q(x)$ ist.