Euklidischer Algorithmus (ggT)
Einführung
Mit dem euklidischen Algorithmus lässt sich der größte gemeinsame Teiler (kurz ggT.) zweier natürlicher Zahlen berechnen. Der euklidische Algorithmus führt in jedem Schritt eine Division mit Rest aus.
Er beginnt mit den beiden Zahlen a und b = r0 deren größter gemeinsamer Teiler bestimmt werden soll. In jedem weiteren Schritt wird mit dem Divisor und dem Rest des vorhergehenden Schritts eine erneute Division mit Rest durchgeführt. Und zwar so lange, bis eine Division aufgeht, das heißt, der Rest Null ist. Der letzten Division ist dann der größte gemeinsame Teiler.
Beispiel
Der größte gemeinsame Teiler von 1071 und 1029 wird mit dem Euklidischen Algorithmus wie folgt berechnet:
Man hat die zwei Zahlen a=1071 und b=1029.
Also ist r1=21 der größte gemeinsame Teiler von 1071 und 1029:
ggT(1071,1029)=21