Algorithmus zur „Zerlegung“ eines Polynoms.

Seien P(X) und S(X) Polynome vom Grad p bzw. s in einer Variablen X über einem Körper \({\mathbb{K}}\). Ist p ≤ s, dann gibt es eindeutig bestimmte Polynome Q(X) und R(X) mit R(X) ≡ 0 oder Grad R(X) < p, so daß gilt

\begin{eqnarray}S(X)=Q(X)\cdot P(X)+R(X).\end{eqnarray}

Das Polynom Q(X) heißt Quotient der Division von S(X) durch P(X). Der Quotient besitzt den Grad s − p. Das Polynom R(X) heißt Rest der Division.

Die Durchführung der Division erfolgt durch sukzessive Subtraktion eines geeigneten skalaren Vielfachen von

\begin{eqnarray}{X}^{s-p-k}\cdot P(X)\,\,\,\,\rm{f}\rm{\ddot{u}}\rm{r}\,\,\,\,k=0,\ldots, s-p\end{eqnarray}

Die skalaren Koeffizienten \({\alpha }_{k}\in {\mathbb{K}}\) sind so zu wählen, daß sich der Grad des Rests mindestens um Eins erniedrigt.

Spätestens für k = (s − p) verschwindet die Differenz oder sie besitzt einen Grad, der kleiner als p ist. Das Quotientenpolynom Q(X) ist gegeben durch

\begin{eqnarray}Q(X)=\displaystyle \sum _{k=0}^{s-p}{\alpha }_{k}{X}^{s-p-k}.\end{eqnarray}

Das Restpolynom ist die zuletzt berechnete Differenz beim Abbruch des Algorithmus (vgl. auch Euklidischer Algorithmus).