Euklidischer Algorithmus/Langsame Version/Aufgabe/Lösung

Aus Wikiversity


  1. Der Algorithmus ersetzt sukzessive

    der größte gemeinsame Teiler ist also .

  2. Wenn ist, so hört der Algorithmus auf. Wenn genau eine Zahl ist, so ist das Folgepaar und dann hört der Algorithmus auf. Es sei also ohne Einschränkung

    Das Folgepaar ist dann und beide Zahlen sind kleiner als . D.h. unter dieser Voraussetzung wird das Maximum mit jedem Rechenschritt kleiner. Da sich alles innerhalb der natürlichen Zahlen abspielt, bricht das Verfahren irgendwann ab.

  3. Bei ist diese Zahl auch der größte gemeinsame Teiler. Wir zeigen, dass sich bei jedem Rekursionsschritt, bei dem (es sei wieder ) durch ersetzt wird, der größte gemeinsame Teiler der beiden Paare übereinstimmt. Dazu muss man nur zeigen, dass und einerseits und und andererseits die gleichen gemeinsamen Teiler haben. Es sei also und und . Dann ist

    ebenfalls ein Vielfaches von . Wenn umgekehrt und ist, so ist

    ebenfalls ein Vielfaches von .

  4. Wir betrachten das Paar . Der euklidische Algorithmus liefert

    und ist fertig. Die Variante ersetzt durch , sie braucht also Schritte, um die Abbruchbedingung zu erreichen.