ggT für Polynomen

Wissenschaft Mathematik
#1

Hallo,

nach dem ich in meiner letzten Frage nach dem Modulo mit Polynomen gefragt habe, habe ich jetzt noch ein Verständnisproblem beim Anwendes des Euklids auf Polynome.

Konkret geht es um das folgende Beispiel im Körper \mathbb{Z}_3:
a=2x^2+x+1
b=x^2 + x + 2
Laut Mathematica ist das Ergebnis des Euklidalgorithmuses 1 (PolynomialGCD[2 x^2 + x + 1, x^2 + x + 2, x, Modulus -> 3])

Ich kann dieses Ergebnis aber leider nicht nachvollziehen. Hier sind meine Rechenschritte (ich hoffe man kann es lesen):
a | b | Rest der Division
2x^2+x+1 | x^2+x+2 | 2x
x^2+x+2 | 2x | 2
2x | 2 | 0

Ich bekomme also also für a und b den ggT=2

Da ich den Rest auch mit Mathematica verifiziert habe, frage ich mich wo mein Fehler liegen könnte.

Beste Grüße
G-Fire

#2

Hi,
habe das Ganze nachgerechnet und erhalte 1.
Schritt 1 stimmt:
2x^2+x+1 | x^2 +x+2 | 2x
Schritt 2": anderes Ergebnis
x^2+x+2|2x|x+2
Schritt 3:
2x|x+2|2 + 1R
geht sicxh nicht aus, also ggt = 1

hoffe, das hilft

#3

Hallo,
Vielen Dank für deine Antwort!

Schritt 2": anderes Ergebnis
x^2+x+2|2x|x+2

Die Frage ist wie du auf das Ergebnis kommst? Ich und auch Mathematica (PolynomialMod[x^3 + x + 2, 2 x, Modulus -> 3]) kommen hier auf Rest 2.

Ich bekomme ja den Rest dadurch, dass ich den Grad von a immer weiter reduziere:
a=x^3 + x + 2
Divisor=2 x

a | Divisor | nächste Rechenoperation
x^2+x+2 | 2x | Divisor normalisieren: div=2x*2 = 4x = x
x^2+x+2 | x | div= *x^(2-1)
x^2+x+2 | x^2 | a=a-Divisor
x+2 | x^2 | Hier muss ich doch weitermachen, da der Grad meines aktuellen as größergleich meinem ursprünglichen Divisiors ist.
x+2 | 2x | Divisor normalisieren: div=2x*2 = 4x = x
x+2 | x | div=*x^(1-1)
2 | x | | a=a-Divisor
Grad von a ist kleiner als vom Divisor und somit ist 2 der Rest.

Stimmt an meiner Rechnung etwas nicht? Und wenn ja, warum macht Mathematica es genau so?

#4

Hi,
zunächst einmal: Warum Mathematica was wie macht kann ich nicht beantworten (will ich auch gar nicht)

Ich hatte mir den Algorithmus bei Wikipedia angeschaut und dann auf Polynome nagewendet:
Beispiel: ggt ( 66, 121)

  1. 121 : 66 = 1 + 55R oder anders geschrieben
    121 = 1*66 + 55
  2. 66 : 55 = 1 + 11R oder
    66 = 1*55 + 11
  3. 55 : 11 = 5 + 0R oder
    55 = 5*11 + 0
    daher ist 11 ggt (wie nicht anders zu erwarten)

nun zu deinem Beispiel

  1. 2x^2 + x + 1 : x^2 + x + 2 = 2 + 2xRest (wegen mod 3, Z3)
    oder 2x^2 + x + 1 = 2 *(x^2 + x + 2) + 2x
  2. (x^2 + x + 2) : 2x = 2x + (x+2)Rest
    oder (x^2 + x + 2) = 2x * 2x + x+2
  3. 2x: x+2 = 2 + 1
    oder 2x = 2*(x+2) + 1; geht sich nicht aus, daher ggt = 1

OK?

#5

Hallo;

2x = 2*(x+2) + 1

Tatsache? Wie denn das? Ich dachte, wir rechnen mod 3. :open_mouth:
Und dass (-1)*(-1)+1=0 ist, willst du mir jetzt nicht ernsthaft weismachen, oder?

mfG

#6

Schritt 1 und 2 kann ich nachvollziehen. Schritt 3 ist mir aber völlig unverständlich. Ich komme da auf 2.

2x = 2*(x+2)+2
2x = 2x+4+2 = 2x+6 = 2x

Meine Probe stimmt also.