euklidischer Algorithmus zur Bestimmung des ggT bei Polynomen

31.12.2010, 01:10

Duude

Auf diesen Beitrag antworten »

euklidischer Algorithmus zur Bestimmung des ggT bei Polynomen

Hallo,
ich habe hier zwei Polynome von denen ich den ggT bestimmen möchte.
Sie lauten
$\begin{eqnarray*} P=8x^3-27 \end{eqnarray*}$ und $\begin{eqnarray*} Q=4x^3-12x+9 \end{eqnarray*}$

Ich kenne bis jetzt den euklidischen Algorithmus zur Bestimmung des ggT von Zahlen. Bei Polynomen müsste das aber doch analog gehen. Nur bin ich mir hier wieder nicht sicher, ob ich schauen soll, ob P in Q passt oder andersrum.
Kann es sein, dass das egal ist, da sonst im 1. Schritt das größere Polynom (was auch immer das heißen mag) nicht in das kleinere Polynom passt und sich dann die Reihenfolge der Polynome in nächsten Schritt umdreht?

Ich habe jetzt einfach mal so begonnen:

$\begin{eqnarray*} 8x^3-27=(4x^3-12x+9) \cdot 2 + (24x-18) \end{eqnarray*}$

Dabei ist das in der hinteren Klammer mein Rest.

$\begin{eqnarray*} 4x^3-12x+9= (24x-18)\cdot x^2 +(-20x^3+18x^2-12x+9) \end{eqnarray*}$
$\begin{eqnarray*} (24x-18)=(-20x^3+18x^2-12x+9) \cdot 0 + (24x+18) \end{eqnarray*}$

usw.

Bin ich hier auf dem richtigen Weg? Die Polynome werden ja wieder größer, das stört mich etwas.

Ich würde mich freuen, wenn ihr mir einen Tipp geben könntet, ob das so passt oder was ich falsch mache.

lg
Duude

31.12.2010, 15:04

gotfried

Auf diesen Beitrag antworten »

RE: euklidischer Algorithmus zur Bestimmung des ggT bei Polynomen

Zitat:

Kann es sein, dass das egal ist, da sonst im 1. Schritt das größere Polynom (was auch immer das heißen mag) nicht in das kleinere Polynom passt und sich dann die Reihenfolge der Polynome in nächsten Schritt umdreht?

Also P muss immer das Polynom mit höherem Grad sein. Da bei dir beide Polynome gleichen Grad haben ist die Reihenfolge egal.

In deiner ersten Division steckt ein kleiner Rechenfehler, damit wird dein Rest falsch.

Ansonsten hast du recht. Man verfährt genau wie mit Zahlen, das funktioniert weil Polynome mit Addition und Multiplikation einen Körper bilden.

Deine zweite Division stimmt abgesehen von Fehler im 1.Rest nicht, weil du den Koeffizienten von $\begin{eqnarray*} x^2 \end{eqnarray*}$ vergessen hast. Pro richtigem Algorithmus-Schritt wird der Polynomgrad um mindestens $\begin{eqnarray*} 1 \end{eqnarray*}$ kleiner.

31.12.2010, 18:03

pseudo-nym

Auf diesen Beitrag antworten »

RE: euklidischer Algorithmus zur Bestimmung des ggT bei Polynomen

Zitat:

Original von gotfried
Also P muss immer das Polynom mit höherem Grad sein.

Warum sollte das der Fall sein?

01.01.2011, 16:21

Duude

Auf diesen Beitrag antworten »

Danke erstmal für die Antworten.

Also ich glaube mittlerweile, dass es beim euklidischen Algorithmus egal ist mit welchem Polynom man anfängt. Wenn ich schaue wie oft das größere Polynom in das kleinere passt, ist das Null mal und damit dreht sich die Reihenfolge um und ich muss als nächstes schauen, wie oft das kleinere Polynom in das größere passt.. Also ist es sinnvoll schon so rum anzufangen aber vom Algorithmus her egal. Stimmt ihr mir da zu?

Ich habe das ganze jetzt nochmals durchgerechnet und hoffentlich alle Rechenfehler beseitigt:

Zitat:

In deiner ersten Division steckt ein kleiner Rechenfehler, damit wird dein Rest falsch.

Das habe ich nochmals nachgerechnet, da müsste statt -18 ganz hinten -45 stehen.
$\begin{eqnarray*} 8x^3-27=(4x^3-12x+9) \cdot 2 + (24x-45) \end{eqnarray*}$

Und damit folgt:

$\begin{eqnarray*} 4x^3-12x+9= (24x-45)\cdot (\frac{1}{6}x^2+\frac{5}{16}x + \frac{11}{128})+12\frac{111}{128} \end{eqnarray*}$

Jetzt weiß ich nicht mehr genau, wie ich weiterrechnen soll. Ich habe ja als Rest nur noch eine Zahl $\begin{eqnarray*} 12 \frac{111}{128} \end{eqnarray*}$
Also müsste ich eigentlich rechnen

$\begin{eqnarray*} (24x-45) : 12\frac{111}{128} \end{eqnarray*}$ . Aber das ist ja gar keine Polynomdivision mehr...

Wie mache ich denn jetzt weiter?

01.01.2011, 19:13

gotfried

Auf diesen Beitrag antworten »

RE: euklidischer Algorithmus zur Bestimmung des ggT bei Polynomen
@pseudo-nym:
gemeint ist das nur als Festlegung für die Polynomdivision: P:Q. Da muss halt P höheren Grad als Q haben, sonst dreht man sie eben um.

01.01.2011, 19:29

Elvis

Auf diesen Beitrag antworten »

@Duude . Jetzt dividierst du mit Rest 0, womit der euklidische Algorithmus beendet ist.

Anzeige

01.01.2011, 19:34

gotfried

Auf diesen Beitrag antworten »

Das ist schon noch eine Polynomdivision, weil noch $\begin{eqnarray*} x^0 \end{eqnarray*}$ da steht. Die ist ja dann ohne Rest ausführbar und du bist fertig.

01.01.2011, 20:02

pseudo-nym

Auf diesen Beitrag antworten »

RE: euklidischer Algorithmus zur Bestimmung des ggT bei Polynomen

Zitat:

Original von gotfried
@pseudo-nym:
gemeint ist das nur als Festlegung für die Polynomdivision: P:Q. Da muss halt P höheren Grad als Q haben, sonst dreht man sie eben um.

Diese Festlegung ist überflüssig, denn P muss nicht den höheren Grad haben. Wenn $\begin{eqnarray*} \deg(P) < \deg(Q) \end{eqnarray*}$ so passiert dieses "umdrehen" im ersten Schritt des euklidischen Algorithmus' von selbst.

01.01.2011, 20:12

gotfried

Auf diesen Beitrag antworten »

RE: euklidischer Algorithmus zur Bestimmung des ggT bei Polynomen
@pseudo-nym:
klar, du hast recht.
Wir sparen uns mit der Festlegung nur diesen Schritt. Aber notwendig ist sie nicht.

01.01.2011, 20:21

Duude

Auf diesen Beitrag antworten »

ok, ich erhalte also dann als letzten Schritt:

$\begin{eqnarray*} (24x-45) = 12 \frac{111}{128} \cdot ( \frac{24}{12 \frac{111}{128}}x - \frac{45}{12 \frac{111}{128}})+0 \end{eqnarray*}$

Damit ist der Rest 0 und der euklidische Algorithmus beendet.

Ursprünglich wollte ich ja den ggT der beiden Polynome bestimmen. Wo genau finde ich den jetzt in meinem Algorithmus? Ich muss ihn ja irgendwo am Ende finden.

01.01.2011, 21:15

gotfried

Auf diesen Beitrag antworten »

$\begin{eqnarray*} x^0 \end{eqnarray*}$ also 1 ist ein ggT. Damit sind die Polynome teilerfremd. Bei Polynomen sind die ggT bis auf Multiplikation einer Einheit eindeutig, deshalb ist 1 oder auch $\begin{eqnarray*} 12\frac{111}{128} \end{eqnarray*}$ ein ggT und nicht der ggT.

01.01.2011, 21:36

Duude

Auf diesen Beitrag antworten »

echt, der ggT ist nicht eindeutig?

Aber ggT(30,12)=6 ist doch eindeutig in den ganzen Zahlen.

Zitat:

Bei Polynomen sind die ggT bis auf Multiplikation einer Einheit eindeutig

Wenn wir uns jetzt wie hier im Polynomring befinden, sind alle Polynome mit Grad 0 also alle Zahlen Einheiten.
Wenn also ein ggT =1 ist, könnte ich auch schreiben ggT=3 oder ggT = 18203?

Aber wo genau erkenne ich den (oder besser: einen) ggT am Algorithmus? Das habe ich noch nicht erkannt...
Vllt kannst du mir ein Bsp geben, wo ein ggT nicht gerade 1 ist sondern dementsprechend ein Polynom? Also z.B. nur die letzte Zeile, dass ich erkennen kann, wo genau ich den ggT im Algorithmus finde.

Und wäre er dann auch nicht eindeutig definiert, wenn er ein Polynom ist? Also wenn z.B. der ggT=X+1 wäre, dann könnte ich ihn ja mit der Einheit 3 multiplizieren und erhalte als weiteren ggT 3X+3.
Stimmt das so?

02.01.2011, 10:47

gotfried

Auf diesen Beitrag antworten »

Zitat:

Wenn wir uns jetzt wie hier im Polynomring befinden, sind alle Polynome mit Grad 0 also alle Zahlen Einheiten.
Wenn also ein ggT =1 ist, könnte ich auch schreiben ggT=3 oder ggT = 18203?

Zitat:

Und wäre er dann auch nicht eindeutig definiert, wenn er ein Polynom ist? Also wenn z.B. der ggT=X+1 wäre, dann könnte ich ihn ja mit der Einheit 3 multiplizieren und erhalte als weiteren ggT 3X+3. Stimmt das so?

Genau.

Zitat:

Aber wo genau erkenne ich den (oder besser: einen) ggT am Algorithmus? Das habe ich noch nicht erkannt... Vllt kannst du mir ein Bsp geben, wo ein ggT nicht gerade 1 ist sondern dementsprechend ein Polynom? Also z.B. nur die letzte Zeile, dass ich erkennen kann, wo genau ich den ggT im Algorithmus finde.

Rechne doch einfach mal $\begin{eqnarray*} ggT(x^2,x) \end{eqnarray*}$ , dann siehst du es.

02.01.2011, 11:24

Elvis

Auf diesen Beitrag antworten »

Zitat:

Original von Duude
echt, der ggT ist nicht eindeutig?

Aber ggT(30,12)=6 ist doch eindeutig in den ganzen Zahlen.

Der ggT ist immer eindeutig bis auf Einheiten, das gilt auch hier, denn es ist ggT(30,12)={+6,-6}. Da es in $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ genau zwei Einheiten gibt, wählt man als einen Vertreter des ggT normalerweise den positiven. Bei Polynomen kann man immer ein normiertes Polynom als ggT wählen (höchster Koeffizient 1).

02.01.2011, 21:44

Duude

Auf diesen Beitrag antworten »

Zitat:

Rechne doch einfach mal $\begin{eqnarray*} ggT(x^2,x) \end{eqnarray*}$ , dann siehst du es.

Wenn ich hier eine Polynomdivision mache, erhalte ich

$\begin{eqnarray*} x^2/x = x \end{eqnarray*}$ .

Damit ist x ein ggT(x,x²). Ein anderer ggT wäre z.B. 3x oder -7x.

Bei dem Beispiel sieht man einen ggT ja auch direkt...

Deshalb gibt man auch bei Polynomen als ggT stets 1 an, wenn man irgendeine Zahl (ohne x) rausbekommt.

Zitat:

Der ggT ist immer eindeutig bis auf Einheiten, das gilt auch hier, denn es ist ggT(30,12)={+6,-6}. Da es in $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ genau zwei Einheiten gibt, wählt man als einen Vertreter des ggT normalerweise den positiven. Bei Polynomen kann man immer ein normiertes Polynom als ggT wählen (höchster Koeffizient 1).

Würde normiert dann in dem Fall dann auch heißen

$\begin{eqnarray*} 3x^2 +x+4 \end{eqnarray*}$ ?

Ich hatte im Kopf dass normiert bedeutet, dass der Leitkoeffizient = 1 ist...

Nach deiner Definition wäre normiert aber einfach dann wenn der höchste Koeffizient 1 ist, unabhängig davon ob es der Leitkoeffizient ist.

03.01.2011, 13:06

Elvis

Auf diesen Beitrag antworten »

Mit "höchster Koeffizient" meinte ich "Koeffzient des Monoms mit höchstem Grad" , und das ist der Leitkoeffizient.

03.01.2011, 18:10

Duude

Auf diesen Beitrag antworten »

ach so.
Dann ist mir alles klar smile

smile

Danke an alle Helfenden...

Duude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »