Größter gemeinsamer Teiler von Polynomen mit unübersichtlichen Zahlen

Question

Aufgabe:

Gesucht ist der ggT von

$$q(x)=x^5-3\,x^4-4\,x^3-2\,x^2+88\,x-80 $$

$$p(x)=x^4+2\,x^3-80\,x^2-336\,x-640 $$

Problem/Ansatz:

Mit Euklidischem Algorithmus. Erster Schritt q/p gibt :(x-5) Rest $$86\,x^3-66\,x^2-592\,x-3280$$ 

Normalerweise würde ich jetzt p durch diesen Rest dividieren. Dafür müsste ich ja eigentlich die ganze Formel durch 86 (oder 43, wenn ich vorher durch 2 kürze) teilen. Wenn ich das tue wird das ganze sehr schnell sehr unübersichtlich. Habe ich hier einen Denkfehler oder gibt es noch einen anderen Ansatz das ggT herauszubekommen? Oder muss ich mich einfach durchbeißen und das ganze mit den Brüchen durchziehen?

Answer 1

Es gibt natürlich einen anderen Weg.

Das Problem ist: Der ggT lässt sich mit dem Euklidischen Algorithmus nur in euklidischen Ringen berechnen. Deine Polynome sind aus \( \mathbb{Z}[x] \), das ist aber kein euklidischer Ring. Um den ggT berechnen zu können musst du die Polynome also als Elemente von \( \mathbb{Q}[x] \) auffassen. Das Ergebis wird dann aber i.A. auch Koeffizienten in \( \mathbb{Q} \) haben.

ggTs sind eindeutig bis auf Multiplikation mit Einheiten. Die Einheiten von  \( \mathbb{Q}[x] \) sind die Einheiten von  \( \mathbb{Q}\) und das sind alle rationalen Zahlen ungleich 0. Wenn wir den ggT aus dem EA also mit einer rationalen Zahl ungleich 0 multiplizieren kommt da wieder ein ggT raus. Wenn wir als rationale Zahl jetzt den Hauptnenner aller Koeffizienten des EA ggTs wählen, dann bekommen wir nach der Multiplikation mit dem Hauptnenner einen ggT mit Koeffizienten in \(  \mathbb{Z} \).

Dein Ziel ist also prinzipiell erreichbar.

Ein Algorithmus der direkt den ggT in  \( \mathbb{Z}[x] \) berechnet ist z.B. der primitive euklidische Algorithmus mit der Pseudo-Division.

Siehe z.B. hier

https://en.m.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Pseudo-remainder_sequences