Euklidischer Algorithmus/Langsame Version/Aufgabe/Lösung

1. Der Algorithmus ersetzt sukzessive

   $(7,3)\mapsto (4,3)\mapsto (3,1)\mapsto (2,1)\mapsto (1,1),$

   der größte gemeinsame Teiler ist also ${}1$.

2. Wenn ${}a=b$ ist, so hört der Algorithmus auf. Wenn genau eine Zahl ${}0$ ist, so ist das Folgepaar ${}(c,c)$ und dann hört der Algorithmus auf. Es sei also ohne Einschränkung

   ${}a>b>0\,.$

   Das Folgepaar ist dann ${}(a-b,b)$ und beide Zahlen sind kleiner als ${}a$. 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 ${}a=b$ ist diese Zahl auch der größte gemeinsame Teiler. Wir zeigen, dass sich bei jedem Rekursionsschritt, bei dem ${}(a,b)$ (es sei wieder $a\geq b$) durch ${}(a-b,b)$ ersetzt wird, der größte gemeinsame Teiler der beiden Paare übereinstimmt. Dazu muss man nur zeigen, dass ${}a$ und ${}b$ einerseits und ${}a-b$ und ${}b$ andererseits die gleichen gemeinsamen Teiler haben. Es sei also ${}t\in \mathbb {N}$ und ${}a=tm$ und ${}b=tn$. Dann ist

   ${}a-b=mt-nt=(m-n)t\,$

   ebenfalls ein Vielfaches von ${}t$. Wenn umgekehrt ${}a-b=rt$ und ${}b=st$ ist, so ist

   ${}a=a-b+b=rt+st=(r+s)t\,$

   ebenfalls ein Vielfaches von ${}t$.

4. Wir betrachten das Paar ${}(n,1)$. Der euklidische Algorithmus liefert

   ${}n=n\cdot 1+0\,$

   und ist fertig. Die Variante ersetzt ${}(n,1)$ durch ${}(n-1,1)$, sie braucht also ${}n-1$ Schritte, um die Abbruchbedingung ${}(1,1)$ zu erreichen.

Zur gelösten Aufgabe