Euklidischer Algorithmus/Langsame Version/Aufgabe/Lösung
- Der Algorithmus ersetzt sukzessive
der größte gemeinsame Teiler ist also .
- 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.
- 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 .
- Wir betrachten das Paar . Der euklidische Algorithmus liefert
und ist fertig. Die Variante ersetzt durch , sie braucht also Schritte, um die Abbruchbedingung zu erreichen.