GGT zweier Zahlen

Es wird der größte gemeinsame Teiler zweier Zahlen a und b nach dem Euklidischen Algorithmus berechnet.

a = b =


Beispiel für dieses Rechenverfahren:

ggT(3324,636) = ggT(636,144) weil: 3324 % 636 = 144
ggT( 636,144) = ggT(144, 60) weil:  636 % 144 =  60
ggT( 144, 60) = ggT( 60, 24) weil:  144 %  60 =  24
ggT(  60, 24) = ggT( 24, 12) weil:   60 %  24 =  12
ggT(  24, 12) = 12 weil:   24 %  12 =   0

Idee von Euklid: Der ggT zweier Zahlen steckt im Rest der Division, wenn man die größere durch die kleinere dividiert.