Mit dem euklidischen Algorithmus lässt sich der grösste gemeinsame Teiler zweier natürlichen Zahlen bestimmen. Das Verfahren ist nach dem griechischen Mathematiker Euklid benannt, der es in seinem Werk «Die Elemente» beschrieben hat.

Der Algorithmus besteht aus einer fortwährenden Division mit Rest, wobei im ersten Schritt die grössere Zahl durch die kleinere dividiert wird. Im zweiten Schritt wird die kleinere Zahl zum neuen Dividenden und der Rest zum neuen Divisor. Diese Schritte setzen sich fort, bis ein Rest von 0 oder 1 resultiert. Bei Rest 0 entspricht der letzte verwendete Divisor dem ggT der beiden Zahlen. Bei Rest 1 sind die beiden Zahlen teilerfremd.

Dieses Skript visualisiert den euklidischen Algorithmus mit seinen einzelnen Rechenschritten für beliebige natürliche Zahlen.

Zahl 1

Zahl 2