Der ggT zweier Zahlen ist die größte Zahl, durch die beide Zahlen teilbar sind.
Ist der größte gemeinsame Teiler 1, so sind a und b teilerfremd.
Beispiel:
a = 10; b = 15
T(10) = {1; 2; 5; 10}
T(15) = {1; 3; 5; 15}
Die gemeinsamen Teiler sind hier 1 und 5. Der größte gemeinsame Teiler ist daher 5. a und b sind nicht teilerfremd.
Euklidischer Algorithmus (klassisch)
Mit dem Euklidischen Algorithmus wird der größte gemeinsame Teiler von zwei Zahlen a und b bestimmt.
Dabei wird immer die kleinere von der größeren Zahl abgezogen bis diese gleich sind. Es gelten folgende Regeln:
ggT(a, b) = ggT(a-b, b), wenn a > b
ggT(a, b) = ggT(a, b-a), wenn b > a
ggT(a, a) = a
ggT(10, 15) = ggT(10, 5) = ggT(5, 5) = 5.
a
b
10
15
10
5 (= 15 - 10)
5 (= 10 - 5)
5
Euklidischer Algorithmus (modern)
Mit dem Euklidischen Algorithmus wird der größte gemeinsame Teiler von zwei Zahlen a und b
durch das mehrmalige Ausführen der Division mit Rest (a = b * q + r) berechnet.
Berechne den ggT(, )
Hier wird die Rechnung zur Bestimmung des ggT(1410, 137) Schritt für Schritt durchgeführt: