Mit dem euklidischen Algorithmus lässt sich der größte gemeinsame Teiler (ggT) zweier natürlicher Zahlen bestimmen.
Will man z. B. den größten gemeinsamen Teiler von 546 und 441 finden, so wird gemäß des Euklidischen Algorithmus wie folgt verfahren:
| 1. Schritt: Subtrahiere 441 so oft wie möglich von 546. |
546 - 1 · 441 = 105 |
| 2. Schritt: Subtrahiere 105 so oft wie möglich von 441. |
441 - 4 · 105 = 21 |
| 3. Schritt: Subtrahiere 21 so oft wie möglich von 105. |
105 - 5 · 21 = 0 |
Der letzte von Null verschiedene Rest, d. h. in diesem Fall die 21 ist der größte gemeinsame Teiler von 546 und 441.
Aufgabe
Bestimmen Sie mit Hilfe des euklidischen Algorithmus den ggT von 1012 und 124 !
Veranschaulichung des euklidischen Algorithmus
Es ist erstaunlich, dass dieses Verfahren immer den ggT liefert.
Warum das so ist, bekommen Sie im folgenden Video am obigen Beispiel von 546 und 441 erklärt. Wir wissen bereits, dass der ggT dieser beiden Zahlen 21 ist. Achten Sie beim Betrachten insbesondere darauf, dass der ggT 21 schlussendlich alle Strecken restlos ausmisst.
Versuchen Sie analog eine Veranschaulichung für den ggT von 1012 und 124 zu zeichnen. Sehen Sie sich dazu das Video ggf. mehrfach an und stoppen Sie an zentralen Stellen.
