Widersprüchliche Erklärung d. erweiterten Euklidschen Algorithmus

Neue Frage »

phi Auf diesen Beitrag antworten »
Widersprüchliche Erklärung d. erweiterten Euklidschen Algorithmus
Hallo alle,
Seit 5 Stunden dreh´ich mich im Kreis beim Versuch diese Erklärung von Wikipedia zu verstehen, aber der eine Teil scheint dem anderen zu widersprechen. traurig
"
1.Setze m = a, n = b, s = 1, t = 0, u = 0, v = 1
2.Berechne q und r mit m = q * n + r (Division mit Rest)
3.Setze m = n, n = r, u' = s - q * u, v' = t - q * v
4.Setze s = u, t = v, u = u', v = v'
5.Falls n nicht gleich 0 gehe zu Schritt 2.

Nach Beendigung ist ggT(a,b)=m=sa+tb. "

Aber wenn ich die oben genannten Schritte anwende (z.B. für a=5 und b=27) komm ich in eine endlos-Schleife, bei der immer wieder nur die ersten beiden Zeilen a=... und b=... der nachfolgenden Form vorkommen! geschockt
"
Man kann dieses Vorgehen in der folgenden Form übersichtlich darstellen:



Man zieht immer von der vorletzten Zeile ein geeignetes Vielfaches der letzten Zeile ab, um die nächste Zeile zu erhalten. Auf der linken Seite der Gleichungen wird der gewöhnliche euklidische Algorithmus durchgeführt, also erhält man schließlich eine Darstellung

ggT(a,b)=xa+yb. "

Kann jemand mit mir Schritt für Schritt das Beispiel a=5 und b=27 durchgehen ? Durch Probieren weilß ich das x=11 und y=2 ist. Aber ich will dieses Verfahren verstehen. Hilfe

Danke, phi
Leopold Auf diesen Beitrag antworten »

5 = 27·0 + 5
27 = 5·5 + 2
5 = 2·2 + 1
2 = 1·2 geht auf; daher ist 1 der ggT.

Wenn man ungeschickterweise mit der kleineren der beiden Zahlen anfängt (hier 5 statt 27), liefert der Algorithmus die überflüssige erste Zeile. Man fängt also besser mit der größeren Zahl an, dann geht es gleich mit der zweiten Gleichung los.

Und jetzt die vorletzte Zeile nach 1 auflösen:
1 = 5 - 2·2

Zweite Gleichung nach 2 auflösen und einsetzen:
1 = 5 - 2·2 = 5 - (27 - 5·5)·2 = 5 - 27·2 + 5·10 = 5·11 - 27·2
phi Auf diesen Beitrag antworten »

Vielen Dank Leopold,

Man macht also erstmal den normalen Eukl. Algo. und geht dann rückwärts wieder hoch und setzt ein. smile

Die Erklärung von Wikipedia sieht aber so gaaanz anders aus (?)
AD Auf diesen Beitrag antworten »

Ganz einfach, weil Leopolds Vorgehen etwa folgendermaßen lautet: Erstmal kümmern wir uns um die Berechnung des ggT. Wenn wir den dann haben, setzen wir rückwärts in unsere Zwischenrechnungen ein und erhalten die gesuchten Koeffizienten.

Das ist didaktisch nicht von der Hand zu weisen, aber algorithmisch gesehen keine sonderlich geschickte Variante - schließlich muss die ganze "Berechnungshistorie" irgendwie zwischengespeichert werden. Der Algorithmus auf der Wikipedia-Seite vermeidet das, indem er während der ggT-Berechnung die gesuchten Koeffizienten (bzw. Zwischenwerte dahin) parallel mitführt, ohne die gesamte Berechnungshistorie mitführen zu müssen - es reichen die jeweils aktuellen Werte.
phi Auf diesen Beitrag antworten »

Vielen dank Arthur,

Ich hab´s ! Freude (Hab deswegen meinen wirren ersten Versuch wegeditiert)

Sei a=27 und b=5.

1.Schritt: Setze m=27, n=5 und s=1, t=0 und u=0, v=1.

2.Schritt: m:n=27:5= 5 =q, r=2.

3.Schritt: Setze m=n=5, n=r=2 und u'=s-qu =1, v'=t-qv=(-5).

4.Schritt: Setze s=u=0, t=v=1 und u=u'=1, v=v'=(-5).

5. n nichtgleich 0 --> 2. Schritt


2'.Schritt: 5:2=2=q, r=1.

3'.Schritt: Setz m=2, n=1 und u'=0-21=(-2), v'=1-2(-5)=11

4'.Schritt: Setz s=u=1, t=v=(-5) und u=u'=( -2), v=v'=11.

5.--->2.Schritt

2''.Schritt: 2:1=2=q, r=0

3''.Schritt: m=1, n=r=0--> Abbruch.

4''.Schritt: s=u=(-2), t=v=11 ----> 1=(-2)27 +115.

Und damit hat man b'=11 für bb' mod a = 1, also das multiplikative Inverse mod a zu b gefunden.

Nun ist auch die in Wikipedia dargestellte übersichtliche Form kein PAL- (Problem-anderer-Leute-)Feld mehr:
Es ist immer für aktuelle m, s und t : m=sa+tb



smile
Leopold Auf diesen Beitrag antworten »

Und hier ein rekursiver Algorithmus in Pascal.

Zunächst deklariert man den Typ
code:
1:
2:
type
  ggTTyp = record g,u,v: Integer; end;


In ihm soll den aufnehmen, während die Werte der Linearkombination sind.

Dann erledigt die Funktion ggT die Berechnung:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
function ggT(a,b: Integer): ggTTyp;
var
  r,q,u: Integer;
  y:     ggTTyp;
begin
  r:=a mod b; q:=a div b;
  if r=0
  then begin
    y.g:=b; y.u:=0; y.v:=1;
  end
  else begin
    y:=ggT(b,r);
    u:=y.v; y.v:=y.u-u*q; y.u:=u;
  end;
  ggT:=y;
end;


Beispiel: ggT(27,5)=(1,-2,11)
 
 
phi Auf diesen Beitrag antworten »

Hmm, intressant!

Eine schöne Abrundung für diesen Thread.

P.S.: Hiermit nehme meine Verunglimpfung der Wikipedia-Erklärung zurück. (Es gilt: Keine Panik ) Vielleicht kann man Wikipedia durch das Beispiel ergänzen.
Neue Frage »
Antworten »



Verwandte Themen

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