zu s&a ggt von zwei polynomen

[maus]

huhu,

hat einer eine idee wie man das noch mal macht...
wurde in der klausur vom 20.9.02 verlangt?

[Taurin]

Eine Möglichkeit: Faktorisiere beide Polynome (z.b. durch Nullstellen bestimmen, mit Kronecker ...). Das Produkt aller gemeinsamer Faktoren ist dann der ggT. In der Klausur ging das nicht, da das Polynom [tex]2 x^2 + 5x - 12[/tex] irreduzibel ist, da die Nullstellen keine ganzen Zahlen sind.

[laser]

Machs einfach mit dem normalen Euklidischen Algorithmus nur, dass jetzt bei jedem schritt eine Polynomdivision durchzuführen ist.
Siehe http://de.wikipedia.org/wiki/Euklidischer_Algorithmus.

@taurin: den kronecker algorithmus hab ich noch nicht so richtig verstanden, vielleicht kannst du den mal erklären (bei klappte das immer nicht ...)

[Br3ndel]

Bist du dir sicher, dass dieses Polynom irreduzibel ist? Ich habe als ggT [tex]2\,*\,(x\,-\,\frac{3}{2})[/tex] heraus (wenn ich das richtig in Erinnerung habe). [tex]\frac{3}{2}[/tex] ist zwar keine ganzzahlige Nullstelle, aber ist das wirklich ein Kriterium für Irreduzibilität?

Und zum Algorithmus von Kronecker...

Ich bin mir nicht ganz sicher, ob er so funktioniert, wie ich es mir vorstelle:

1) Setze ein a_i in das zu zerlegende Polynonom P ein, bilde also P(a_i).
2) Als Ergebnis erhält man eine rationale (oder ganze?) Zahl b, ein Linearfaktor von P ist also auf jeden Fall (x + c), wobei c entweder b oder einer der ganzzahligen Teiler von b ist.

Stimmt das so? Und falls ja, wo ist da der Unterschied bzw. Vorteil zum Nullstellenraten?

Br3ndel

[laser]

Moin!

Das ergebnis sollte richtig sein (http://www.arndt-bruenner.de/mathe/scri ... nomggt.htm). Es ist auf jeden Fall reduzierbar, da
2*x-3 Element von Z[x]
ist. Mit den Nullstellen hat das nichts zu tun.

[Taurin]

Ok, mein Argument mit den Nullstellen ist quark, das Polynom ist reduzibel.

Zu Kronecker (soweit ich das verstanden hab):
Sei P das Polynom, dass wir faktoriesieren wollen, mit deg P = n. Nun schreiben wir [tex]P = Q \cdot R[/tex], mit deg [tex]Q = \frac{n}{2} =: s[/tex] (abrunden - wie macht man Gaussklammern mit LaTeX?).

Schritt 1: Wähle s+1 ganze Zahlen [tex]a_i, i = 0..s[/tex]. Dann gilt [tex]Q(a_i)[/tex] teilt [tex]P(a_i)[/tex]. Am besten wählt man die [tex]a_i[/tex] so, dass die [tex]P(a_i)[/tex] prim sind.
Schritt 2: Finde alle Teiler der [tex]P(a_i)[/tex] und bilde alle Kombinationen der möglichen Teiler. Es gibt nur endlich viele solcher Kombinationen.
Schritt 3: Bilde für jede Kombination das Interpolationspolynom mit dem Grad <= s. Teilt das Interpolationspolynom P, dann haben wir einen Teiler gefunden. Teilt kein Interpolationspolynom P, dann ist P irreduzibel.

Die Laufzeit ist exponentiell, so richtig toll ist der Algorithmus also nicht.

edit: Noch ein Beispiel mit dem Polynom von oben: [tex]P(x) = 2x^2 + 5x - 12[/tex]

[tex]s = 1, a_0 = -1, a_1 = 1[/tex]
[tex]P(-1) = -15 = - 1 \cdot 3 \cdot 5[/tex]
[tex]P(1) = - 1 \cdot 5[/tex]
Wählen wir jetzt [tex]Q(-1) = 1[/tex] und [tex]Q(1) = 5[/tex], bekommen wir den Teiler [tex]Q(x) = 2x + 3[/tex]

[Br3ndel]

Vielen Dank, so ergibt das Sinn!

Br3ndel

[turing]

Also wenn ich das mit Euklid, so wie im Skript mache, komme ich auf einen ggt von 30x-45. Das ist dasselbe, bis auf einen Faktor von 15.
Müssen die Koeffizienten ganzzahlig sein oder reichen Brüche? Im Skript ist immer von [tex]P \in \mathbb{Q[x]}[/tex] die Rede.

[Lady_X]

Kronecker

[Hamburger]

Also wenn ich das mit Euklid, so wie im Skript mache, komme ich auf einen ggt von 30x-45. Das ist dasselbe, bis auf einen Faktor von 15.
Müssen die Koeffizienten ganzzahlig sein oder reichen Brüche? Im Skript ist immer von [tex]P \in \mathbb{Q[x]}[/tex] die Rede.

Also da der GGT ja dabei der selbe bleibt würde ich mal sagen, das ist Jacke wie Hose. Aber der Schönheit halber könnte man sich ja auf normierte Form einigen, sprich aus 30x-45 machen wir einfach x-3/2.