Erweiterter Euklid Polynome Restklassen

Neue Frage »

metalbeppi Auf diesen Beitrag antworten »
Erweiterter Euklid Polynome Restklassen
Hallo ich soll für zwei Polynome (p, q) - deren Koeffizienten Restklassen sind - den ggT und zwei weitere Polynome (u, v) bestimmen so dass p * u + q * v den ggT ergibt.

Auf Wikipedia steht ja, dass man mit Restklassen wie mit ganzen Zahlen rechnen kann und man am Schluss die Modulo Reduktion durchführen kann.

Die Angabe:

http://img687.imageshack.us/img687/4796/angabe.jpg

Nun ist es aber so, dass bereits bei der ersten Division während der Ausführung des Algorithmus Brüche als Koeffizienten im Ergebnis und auch im Rest stehen. Was mache ich mit denen, immerhin verrtagen sich diese ja nicht mit den Restklassen, oder?
Mystic Auf diesen Beitrag antworten »
RE: Erweiterter Euklid Polynome Restklassen
Zitat:
Original von metalbeppi
Nun ist es aber so, dass bereits bei der ersten Division während der Ausführung des Algorithmus Brüche als Koeffizienten im Ergebnis und auch im Rest stehen. Was mache ich mit denen, immerhin verrtagen sich diese ja nicht mit den Restklassen, oder?

Leider verschweigst du, um welche Brüche es sich dabei handelt... verwirrt Prinzipiell sind aber Brüche in kein Problem und sie vertragen sich hervorragend mit Restklassen (warum auch nicht???), außer natürlich der Nenner ist 0... Hier ein paar Beispiele:

metalbeppi Auf diesen Beitrag antworten »

Also bei p / q kommt: 1/4x - 1/16 Rest: 9/16x + 25/8; heraus.

Mir ist leider nicht klar, wie du die Brüche jetzt aufgelöst hast
Mystic Auf diesen Beitrag antworten »

Also ich lass jetzt mal die spitzen Klammern und den Index 5 weg, damit die Schreibweise nicht ganz so schwerfällig ist, d.h., 0,1,2,3,4 stehen im Folgenden für die entsprechenden Restklassen in ...

Dann ist 1/4 einfach die Lösung der Gleichung 1=4x in R, desgleichen 1/16 die Lösung von 16x=1 (oder wegen 16=1 besser 1x=1) in R usw. d.h. du musst diese Gleichungen lösen... Zu diesem Zweck würde ich mir mal ein Liste der Stammbrüche 1/2, 1/3 und 1/4, also der multipliikativen Inversen von 2,3,4 berechnen, das macht alles gleich viel einfacher...

Allgemeiner ist es so: In jedem Körper K ist für zwei Elemente nur eine Kurzschreibweise für die eindeutige Lösung von bx=a in K, die man auch als schreiben kann...
metalbeppi Auf diesen Beitrag antworten »

ah ja stimmt, statt zu dividieren kann man auch mit dem Inversen des Divisors multiplizieren, jetzt kapier ichs, Danke!
Neue Frage »
Antworten »



Verwandte Themen

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