Polynomdivision/Z mod 7/x^2+3x+5 durch 3x+4/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\,.$