Polynomdivision

Aufspaltung des Quotienten der Polynome $\;p(x)\in \mathrm{P}^n,\ q(x)\neq 0$ wie folgt:

$$\frac{p(x)}{q(x)} = s(x) + \frac{r(x)}{q(x)}$$

Damit $s(x) \neq 0$ ist und damit die Polynomdivision sinnvoll ist, muss für den Grad der Polynome gelten: $\operatorname{Grad}\ p\ge\operatorname{Grad}\ q$.

Nun wird $\;p(x)$ schrittweise dividiert ( $\;p_0(x) := p(x)$):

$\;s_i(x)$ wird so gewählt, dass $\;(s_i(x) q(x))_n = (p_i(x))_n$, dass also die Koeffizienten der höchsten in $p$ vorkommenden Potenz gleich sind. $\;p_{i+1}(x) := p_i(x) - q_i(x) s(x)$ Gilt $\operatorname{Grad}\ q(x) > \operatorname{Grad}\ p_{i+1}(x)$, so wird abgebrochen. $i$ wird inkrementiert und die Schleife erneut durchlaufen

Nach Abbruch gilt

$$s(x) = \sum_{k=1}^i s_k(x)$$

$$\;r(x) = p_{i+1}(x)$$