Polynomring über Körper/Der euklidische Algorithmus/Bemerkung

Es sei ${}K$ ein Körper und sei ${}K[X]$ der Polynomring über ${}K$. Dies ist ein Hauptidealbereich und daher gibt es zu gegebenen Polynomen ${}P_{1},P_{2},\ldots ,P_{n}$ einen größten gemeinsamen Teiler, und diesen kann man darstellen als Linearkombination der gegebenen Polynome. Es gibt sogar ein effektives Verfahren, eine solche Darstellung explizit zu finden, das man (wie bei den ganzen Zahlen ${}\mathbb {Z}$) den euklidischen Algorithmus nennt. Wir beschränken uns auf den Fall von zwei Polynomen ${}F$ und ${}G$. Man führt nun sukzessive eine Division mit Rest durch und erhält zunächst

$F=Q_{1}G+R_{1}.$

Dann erhält man

$G=Q_{2}R_{1}+R_{2},\,R_{1}=Q_{3}R_{2}+R_{3},\,$

usw., bis schließlich der Rest ${}R_{k}=0$ ist. Dieser Fall muss letztlich eintreten, da sich bei jedem Divisionsschritt der Grad der Reste reduziert. Der vorletzte Rest ist dann der größte gemeinsame Teiler, und man kann durch Zurückrechnen entlang der Gleichungen eine Darstellung dieses ggTs mit

${}F$ und ${}G$ finden.