ggt von Polynomen im F_3 bestimmen

Neue Frage »

AmHa Auf diesen Beitrag antworten »
ggt von Polynomen im F_3 bestimmen
Meine Frage:
Bestimmen sie im Polynomring [x] den ggT d der Polynome f= x^4 + x^3 + x^2 -x +1 und g= x^4 +1, sowie Bezoutkoeffizienten u und v mit d = uf +vg

Meine Ideen:
Eigentlich würde ich das jetzt mit dem Euklid-Algorithmus rechnen und in diesem Fall mit Polynomdivison, habe ich auch gemacht, aber da komme ich nicht auf das richtige Ergebnis, ich weiß nämlich nicht, wie ich den Polynomring [x] da bei der Rechnung berücksichtige..
Danke!
Elvis Auf diesen Beitrag antworten »

Das muss funktionieren, egal wo Du rechnest. Du kannst erst rational rechnen und dann modulo 3 reduzieren oder von vornherein modulo 3 rechnen (d.h. 3=0).
Wie sieht denn deine "falsche "Rechnung aus ?
AmHa Auf diesen Beitrag antworten »

Naja, als ich mit Modulo 3 gerechnet habe, habe ich das f erst mal umgerechnet in x^4+x^3+x^2+2x+1 und nach drei Polynomdivisionen hatte ich das Ergebnis -x^2+2x+1 und den Rest 9x + 3, der ja aber modulo 3 gleich 0 wird. Dann hab ich das nochmal kontrolliert und durch f und g jeweils geteilt und der Rest war wieder 0 modulo 3. Ist das denn richtig ?
Elvis Auf diesen Beitrag antworten »

Nein, das ist nicht richtig. Rest
AmHa Auf diesen Beitrag antworten »

Wie bist du denn drauf gekommen ? Ich komme überhaupt nicht auf die gleiche Lösung..
Elvis Auf diesen Beitrag antworten »

Rest

--------------------------------------


 
 
AmHa Auf diesen Beitrag antworten »

Okay, diesen Schritt hatte ich in meiner Rechnung auch, aber dadurch das der Rest noch so "groß" war, hab ich einfach weiter gemacht. Wieso darf man denn schon beim ersten Schritt aufhören ?
Und wie bekomme ich daraus dann die Bezout-Koeffizienten ?
Elvis Auf diesen Beitrag antworten »

Nein, man darf nicht aufhören ... das war nur der Anfang des Euklidischen Algorithmus https://de.wikipedia.org/wiki/Euklidischer_Algorithmus .
Modulo 3 ist tatsächlich , und der erweiterte euklidische Algorithmus https://de.wikipedia.org/wiki/Erweiterte...her_Algorithmus liefert dann die gesuchten Polynome u und v.

Hier findest Du , also
AmHa Auf diesen Beitrag antworten »

Okay, aber dann war mein Ergebnis ja doch richtig, ich hatte ja -x^2 + 2x +1 und wenn ich jetzt noch mod 3 darauf anwende, dann habe ich ja auch ggt = 2x^2+2x+1
Und danke für den Link, aber ich weiß eigentlich wie man das rechnet, nur mit Zahlen ging es bisher um einiges einfacher.
Diese 'Formel', die du da stehen hast, hatten wir auch so ähnlich in der VL, nur fällt es mir schwer das ganze anzuwenden und irgendwas zuordnen zu können, könntest du da vielleicht bitte noch ein bisschen Klarheit schaffen ?
Elvis Auf diesen Beitrag antworten »

Du hast den Euklidischen Algorithmus durchgeführt, indem Du 3 Polynomdivisionen berechnet hast.
(Zumindest hast Du das behauptet. Weil bei dir ein Rest 9x+3 auftaucht, glaube ich das noch nicht so ganz. Es würde nicht schaden, wenn Du deine Rechnungen offenlegst.)
Schreibe das in die von mir vorgeschlagene Reihenfolge, und dann ist alles klar.
Die erste Division und die euklidische Darstellung sieht so aus :
Rest
AmHa Auf diesen Beitrag antworten »

1.Schritt: (x^4+x^3+x^2-x+1) : (x^4+1)=1 Rest x^3+x^2-x
2.Schritt: (x^4+1) : (x^3+x^2-x)=(x-1) Rest 2x^2-x+1 und das wäre ja mod 3 das gleiche wie 2x^2 +2x+1
Dann hab ich es aber auch nochmal anders probiert und zwar habe ich direkt mod 3 angewendet
1.Schritt: (x^4+x^3+x^2+2x+1) : (x^4+1) = 1 Rest x^3+x^2+2x
2.Schritt: (x^4+1) : (x^3+x^2+2x )=(x-1) Rest -x^2+2x+1
3.Schriit: (x^3+x^2+2x ) : (-x^2+2x+1) = (-x-3) Rest 9x+3 mod 3 = 0

So habe ich das, und leider entdecke ich auch den Fehler nicht..
Elvis Auf diesen Beitrag antworten »

Den 3. Schritt hast Du vergessen.
(x^3+x^2-x) : (2x^2-x+1)=...

modulo 3 heißt er
(x^3+x^2+2x) : (2x^2+2x+1)=2x Rest 0 , denn 2*2=4=1
Da ist weiter kein Fehler, es kommt nur nicht 9x+3 vor.

Der ist der letzte von 0 verschiedene Rest , und nun muss Du nur noch rückwärts in die Formel einsetzen, die ich dir gegeben habe.

Beachte: (Polynom-)Division ist eine Rechenart, der euklidische Algorithmus ist eine bestimmte Form, die Dinge aufzuschreiben.
AmHa Auf diesen Beitrag antworten »

Also durch einsetzen habe ich dann u = (x-1) und v = x
Habe auch eine Probe gemacht, also müsste es eigentlich stimmen.
Vielen Dank für die Hilfe!!
Elvis Auf diesen Beitrag antworten »

Ich habe es noch nicht gerechnet, mache ich auch nicht, denn ich weiß von Euklid, dass es geht. Augenzwinkern
Dein Ergebnis ist falsch, denn
AmHa Auf diesen Beitrag antworten »

(-x + 1) meinte ich, dann stimmt es Augenzwinkern
Elvis Auf diesen Beitrag antworten »

stimmt : smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »