Euklidischer Algorithmus (ggT)

Er beginnt mit den beiden Zahlen a und b = r₀ 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