euklidischer Algorithmus < Moduln/Vektorraum < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Der erweiterte euklidische Algorithmus
Seien a, b [mm] \in [/mm] Z. Der erweiterte euklidische Algorithmus lautet wie folgt:
(1) Ist a = b = 0, so gib das Tripel (0, 0, 0) aus und stoppe.
(2) Ist a = 0 und b [mm] \not= [/mm] 0, so gib das Tripel (0, |b| geteilt durch b , |b|) aus und stoppe.
(3) Ist a [mm] \not= [/mm] 0 und b = 0, so gib das Tripel ( |a| geteilt durch a , 0, |a|) aus und stoppe.
(4) Bilde die Tripel (c0, d0, e0) = ( |a| a , 0, |a|) und (c1, d1, e1) = (0, |b| b , |b|).
(5) Prüfe, ob e1 e0 gilt. Falls nicht, vertausche (c0, d0, e0) und (c1, d1, e1) miteinander.
(6) Berechne eine Darstellung e0 = [mm] q\*e1 [/mm] + r mit q 2 N und 0 [mm] \le [/mm] r [mm] \le [/mm] e1.
(7) Ist r = 0, so gib (c1, d1, e1) aus und stoppe.
(8) Bilde (c2, d2, e2) = (c0 − qc1, d0 − qd1, r).
(9) Ersetze (c0, d0, e0) durch (c1, d1, e1) und (c1, d1, e1) durch (c2, d2, e2) und fahre mit (6)
fort.
a) Zeige, dass der erweiterte euklidische Algorithmus nach endlich vielen Schritten stoppt.
b) Zeige, dass bei Durchlaufen des Algorithmus stets acj + bdj = ej für alle j erfüllt ist.
c) Zeige, dass bei Durchlaufen des Algorithmus in den Schritten (4)-(9) stets ggT(a, b) =
ggT(e0, e1) erfüllt ist.
d) Zeige, dass der Algorithmus ein Tripel (c, d, e) 2 Z3 berechnet, so dass e = ggT(a, b) =
ca + db gilt.
e) Wende den Algorithmus auf a = −40 und b = 14 an und gib an, welche Tripel in den
Schritten (4) und (8) berechnet werden. Stelle den ggT(−40, 14) als Linearkombination
von −40 und 14 dar. |
Hab das Problem, dass ich H1d für weitere Aufgaben, brauche und ich selbst nicht drauf komme, kann mir vielleicht irgendjemand weiterhelfen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Do 31.01.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
