Laufzeit des Euklidischen Algorithmus
Hallo, wäre echt super, wenn mir jemand helfen könnte.
Und zwar suche ich nach einer Möglichkeit zu beweisen, dass sich der Rest im Euklidischen Algorithmus alle zwei Schritte mindestens halbiert. Ich weiß, dass sich der Rest mehr als halbiert, jedoch möchte ich nur beweisen, dass er sich halbiert und das ohne Verwendung von Fibonacci-Zahlen. Ich komme allerdings nicht darauf wie man das machen könnte. Habe gerade ein Brett vor'm Kopf. Im Internet finde ich leider keine Abhilfe. Überall wird nur beschrieben, wie man ermittelt, dass die Laufzeit höchstens 5 mal die Anzahl der Ziffern von b ist -,-!
Danke im vorraus, auch wenn ich mir sicher bin, dass da niemand helfen kann^^!
Mfg KGaru21
Mathematik,
Zahlen,
Zahlentheorie,
Algorithmus,
Beweis