Informatik | Asymmetrische Verschlüsselung | Euklidischer Algorithmus

Größter gemeinsamer Teiler (ggT)

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.

ab
1015
105 (= 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: