# Polynomring/Körper/Division mit Rest/Einführung/Textabschnitt
## Definition

Es sei $K$ ein Körper. Man sagt, dass ein Polynom $T\in K[X]$ ein Polynom $P\in K[X]$ teilt, wenn es ein Polynom $Q\in K[X]$ mit
    $P=TQ\,$
gibt.
Wenn $P$ von $T$ geteilt wird, so sagt man auch, dass $P$ ein Vielfaches von $T$ ist. In $K[X]$ ist es, anders wie in einem Körper, aber ähnlich wie in $\mathbb {Z}$, nicht möglich, ein Element durch ein anderes Element $\neq 0$ zu teilen. Es gibt aber, wie bei $\mathbb {Z}$, einen wichtigen Ersatz dafür, die Division mit Rest.

## Satz

Es sei $K$ ein Körper und sei $K[X]$ der Polynomring über $K$. Es seien $P,T\in K[X]$ Polynome mit $T\neq 0$.
Dann gibt es eindeutig bestimmte Polynome $Q,R\in K[X]$ mit

### Beweis

Wir beweisen die Existenzaussage durch Induktion über den
Grad von $P$. Wenn der Grad von $T$ größer als der Grad von $P$ ist, so ist $Q=0$ und $R=P$ eine Lösung, sodass wir dies nicht weiter betrachten müssen. Bei $\operatorname {grad} \,(P)=0$ ist nach der Vorbemerkung auch $\operatorname {grad} \,(TP)=0$, also ist $T$ ein konstantes Polynom, und damit ist (da $T\neq 0$ und $K$ ein Körper ist) $Q=P/T$ und $R=0$ eine Lösung. Es sei nun $\operatorname {grad} \,(P)=n$ und die Aussage für kleineren Grad schon bewiesen. Wir schreiben $P=a_{n}X^{n}+\cdots +a_{1}X+a_{0}$ und $T=b_{k}X^{k}+\cdots +b_{1}X+b_{0}$ mit $a_{n},b_{k}\neq 0,\,k\leq n$. Dann gilt mit $H={\frac {a_{n}}{b_{k}}}X^{n-k}$ die Beziehung
    ${\begin{aligned}P'&:=P-TH\\&=0X^{n}+{\left(a_{n-1}-{\frac {a_{n}}{b_{k}}}b_{k-1}\right)}X^{n-1}+\cdots +{\left(a_{n-k}-{\frac {a_{n}}{b_{k}}}b_{0}\right)}X^{n-k}+a_{n-k-1}X^{n-k-1}+\cdots +a_{0}.\end{aligned}}$
Dieses Polynom $P'$ hat einen Grad kleiner als $n$ und darauf können wir die Induktionsvoraussetzung anwenden, d.h. es gibt $Q'$ und $R'$ mit
    $P'=TQ'+R'{\text{ mit }}\operatorname {grad} \,(R')<\operatorname {grad} \,(T){\text{ oder }}R'=0.$
Daraus ergibt sich insgesamt
    $P=P'+TH=TQ'+TH+R'=T(Q'+H)+R'\,,$
sodass also $Q=Q'+H$ und $R=R'$ eine Lösung ist. Zur Eindeutigkeit sei $P=TQ+R=TQ'+R'$ mit den angegebenen Bedingungen. Dann ist $T(Q-Q')=R'-R$. Da die Differenz $R'-R$ einen Grad kleiner als $\operatorname {grad} \,(T)$ besitzt, ist aufgrund der Gradeigenschaften diese Gleichung nur bei $R=R'$ und $Q=Q'$ lösbar.
$\Box$
Das Polynom $T$ ist genau dann ein Teiler von $P$, wenn bei der Division mit Rest von $P$ durch $T$ der Rest gleich $0$ ist. Der Beweis des Satzes ist konstruktiv, d.h. es wird in ihm ein Verfahren beschrieben, mit der man die Division mit Rest berechnen kann. Dazu muss man die Rechenoperationen des Grundkörpers beherrschen. Wir geben dazu drei Beispiele, zwei über den rationalen Zahlen und eines über einem endlichen Körper.

## Beispiel

Wir führen die Polynomdivision
    $P=X^{2}+X+2{\text{ durch }}T=X-5$
durch. Es wird also ein quadratisches Polynom durch ein lineares Polynom dividiert, d.h. der Quotient muss vom Grad $1$ und der Rest muss vom Grad $0$ sein. Im ersten Schritt überlegt man, mit welchem Term man $T$ multiplizieren muss, damit das Produkt mit $P$ im Leitterm übereinstimmt. Das ist offenbar $X$. Das Produkt ist
    $X{\left(X-5\right)}=X^{2}-5X\,.$
Die Differenz von $P$ zu diesem Produkt ist
    $X^{2}+X+2-{\left(X^{2}-5X\right)}=6X+2\,.$
Mit diesem Polynom, nennen wir es $P'$, setzen wir die Division durch $T$ fort. Um Übereinstimmung im Leitkoeffizienten zu erhalten, muss man $T$ mit $6$ multiplizieren, dies ergibt
    $6X-30.$
Die Differenz zu $P'$ ist somit
    $6X+2-{\left(6X-30\right)}=32\,.$
Dies ist das Restpolynom und somit ist insgesamt
    $X^{2}+X+2={\left(X+6\right)}{\left(X-5\right)}+32\,.$

## Beispiel

Wir führen die Polynomdivision
    $P=6X^{3}+X+1{\text{ durch }}T=3X^{2}+2X-4$
(über $\mathbb {Q}$) durch. Es wird also ein Polynom vom Grad $3$ durch ein Polynom vom Grad $2$ dividiert, d.h. dass der Quotient und auch der Rest (maximal) vom Grad $1$ sind. Im ersten Schritt überlegt man, mit welchem Term man $T$ multiplizieren muss, damit das Produkt mit $P$ im Leitterm übereinstimmt. Das ist offenbar $2X$. Das Produkt ist
    $2X{\left(3X^{2}+2X-4\right)}=6X^{3}+4X^{2}-8X\,.$
Die Differenz von $P$ zu diesem Produkt ist
    $6X^{3}+X+1-{\left(6X^{3}+4X^{2}-8X\right)}=-4X^{2}+9X+1\,.$
Mit diesem Polynom, nennen wir es $P'$, setzen wir die Division durch $T$ fort. Um Übereinstimmung im Leitkoeffizienten zu erhalten, muss man $T$ mit ${\frac {-4}{3}}$ multiplizieren. Dies ergibt
    $-{\frac {4}{3}}T=-{\frac {4}{3}}{\left(3X^{2}+2X-4\right)}=-4X^{2}-{\frac {8}{3}}X+{\frac {16}{3}}\,.$
Die Differenz zu $P'$ ist somit
    $-4X^{2}+9X+1-{\left(-4X^{2}-{\frac {8}{3}}X+{\frac {16}{3}}\right)}={\frac {35}{3}}X-{\frac {13}{3}}\,.$
Dies ist das Restpolynom und somit ist insgesamt
    $6X^{3}+X+1={\left(3X^{2}+2X-4\right)}{\left(2X-{\frac {4}{3}}\right)}+{\frac {35}{3}}X-{\frac {13}{3}}\,.$

## Beispiel

Wir führen im endlichen Restklassenkörper $\mathbb {Z} /(7)$ die Polynomdivision
    $P=X^{2}+3X+5{\text{ durch }}T=3X+4$
durch. Es wird also ein quadratisches Polynom durch ein lineares Polynom dividiert, d.h. der Quotient muss vom Grad $1$ und der Rest muss vom Grad $0$ sein. Im ersten Schritt überlegt man, mit welchem Term man $T$ multiplizieren muss, damit das Produkt mit $P$ im Leitterm übereinstimmt. Mit was muss man also $3$ in $\mathbb {Z} /(7)$ multiplizieren, um $1$ zu erhalten? Eine Schreibweise wie ${\frac {1}{3}}$ ist hier wenig hilfreich, es muss ein Element aus $\mathbb {Z} /(7)$ sein. Wegen $3\cdot 5=15=1\mod 7$ ist $5$ das inverse Element, man muss also mit $5X$ multiplizieren. Das Produkt ist
    $5X{\left(3X+4\right)}=X^{2}+6X\,.$
Die Differenz von $P$ zu diesem Produkt ist
    $X^{2}+3X+5-{\left(X^{2}+6X\right)}=4X+5\,.$
Mit diesem Polynom, nennen wir es $P'$, setzen wir die Division durch $T$ fort. Um Übereinstimmung im Leitkoeffizienten zu erhalten, muss man $T$ mit $6$ multiplizieren, da ja $3\cdot 6=18=4\mod 7$ ist. Dies ergibt
    $4X+3.$
Die Differenz zu $P'$ ist somit
    $4X+5-{\left(4X+3\right)}=2\,.$
Dies ist das Restpolynom und somit ist insgesamt
    $X^{2}+3X+5={\left(5X+6\right)}{\left(3X+4\right)}+2\,.$