Euklidischer Algorithmus/Langsame Version/Aufgabe

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Wir betrachten eine (einfachere, aber langsamere) Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zu zwei gegebenen natürlichen Zahlen .

Der Algorithmus geht folgendermaßen. Wenn ist, so ersetzte das Paar durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn ist, so ist man fertig und es wird das Ergebnis ausgegeben.

  1. Führe diesen Algorithmus für das Paar durch.
  2. Zeige, dass dieser Algorithmus nach endlich vielen Schritten aufhört.
  3. Zeige, dass dieser Algorithmus korrekt ist, also wirklich den größten gemeinsmen Teiler ausgibt.
  4. Man gebe für jedes ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante Schritte benötigt.
Zur Lösung, Alternative Lösung erstellen