Bestimmung des größten gemeinsamen Teilers zweier Polynome

Teiler und Vielfaches

Das Polynome P(x) ist durch das Polynom teilbar, wenn ein Polynom T(x) existiert, so daß

gilt. Ist P(x) durch Q(x) teilbar, so heißt Q(x) Teiler von P(x), und P(x) heißt Vielfaches von .

Größter gemeinsamer Teiler

Jedes Polynom, das gemeinsamer Teiler der Polynome P(x) und Q(x) ist und gleichzeitig Vielfaches jedes anderen gemeinsamen Teilers dieser beiden Polynome, heißt größter gemeinsamer Teiler der Polynome P(x) und .

Beispiel

.

Wenn P(x) und Q(x) keine gemeinsamen Polynomfaktoren besitzen, dann nennt man sie teilerfremd. Ihr größter gemeinsamer Teiler ist dann eine Konstante.

Euklidischer Algorithmus

Der EUKLIDische Algorithmus ist eine Methode zur Bestimmung des größten gemeinsamen Teilers zweier Polynome P(x) und . P(x) sei vom Grade , Q(x) sei vom Grade , und es gelte . Dann führt man die folgenden Divisionen durch:

1. Division von P(x) durch Q(x) führt auf den Quotienten T₁(x) und den Rest R₁(x):
2. Division von Q(x) durch R₁(x) führt auf den Quotienten T₂(x) und den Rest R₂(x):
3. Division von R₁(x) durch R₂(x) führt auf den Quotienten T₃(x) und den Rest R₃(x) usw:
   Der größte gemeinsame Teiler der beiden Polynome ist dann der letzte von 0 verschiedene Rest Die Methode ist als EUKLIDischer Algorithmus aus der Arithmetik mit natürlichen Zahlen bekannt.

Die Ermittlung des größten gemeinsamen Teilers wird bei der Lösung von Gleichungen eingesetzt, z.B. bei der Abspaltung mehrfacher Wurzeln und bei der Anwendung der STURMschen Methode.