Euklid von Alexandria hat vor rund 2300 Jahren ein geniales Rechenverfahren gefunden, um den größten gemeinsamen Teiler von zwei Zahlen auf einfache Weise zu finden.
Euklid begann mit den beiden Zahlen, von denen der größte gemeinsame Teiler (ggT) gesucht wird und subtrahierte sie voneinander. Dann wiederholte er diesen Schritt mit dem Ergebnis der Rechnung und der kleineren der beiden Ausgangszahlen. Dann mit den beiden kleineren Zahlen der letzten Rechnung usw.. Das Ganze geht so lange, bis Null herauskommt. Das Ergebnis davor ist der gesuchte ggT.
Beispiel: Wir suchen den ggT von \color{red}49 und \color{green}14:
{\color{red}49} - {\color{green}14} = {\color{blue}35}
{\color{blue}35} - {\color{green}14} = {\color{orange}21}
{\color{orange}21} - {\color{green}14} = {\color{purple}7}
{\color{green}14} - {\color{purple}7} = {\color{brown}7}
{\color{purple}7} - {\color{brown}7} = \underline{\underline{0}}
Der gesuchte größte gemeinsame Teiler ist also \color{brown}7.
Hier kannst du die Anwendung dieses Verfahrens üben, das nach seinem Namen „Euklidischer Algorithmus“ genannt wird.
Variante 1: Wiederholtes subtrahieren
Variante 2: Rest der Division
Man kann das Verfahren abkürzen, indem man (wie in der Grundschule) Divison mit Rest ausführt. Dabei interessieren uns vor allem die Reste. Hier rechnen wir im nächsten Schritt immer mit dem Rest (niemals mit dem eigentlichen Ergebnis der Division) und der kleineren der beiden vorigen Zahlen weiter. Bekommt man als Rest 0 heraus, ist man fertig.
Beispiel: Wir suchen wieder den ggT von \color{red}49 und \color{green}14:
{\color{red}49} : {\color{green}14} = {\color{gray}3} \text{ Rest } {\color{purple}7}
{\color{green}14} : {\color{purple}7} = {\color{gray}2} \text{ Rest } {\color{brown}0}
Der gesuchte größte gemeinsame Teiler ist also \color{purple}7.
Du siehst, dass man auf diese Art viel weniger Schritte braucht. Hier noch einmal die selbe Aufgabe wie oben, nur mit dem schnelleren Rechenweg:
Und zum Schluss eine neue Aufgabe mit etwas schwierigeren Zahlen: