Jetzt Rechnen!

Headerbild, verschiedene Zahlen

größte gemeinsame Teiler (ggT)

Mit diesem Online Rechner kann der größte gemeinsame Teiler (ggt) zweier Zahlen berechnet werden.



Berechnung des ggT mit dem euklidischen Algorithmus

Den größten gemeinsamten Teiler kann man sehr schnell und einfach mit dem euklidischen Algorithmus berechnen.

Euklidische Algorithmus:

Dazu teilt man die größere der beiden Zahlen durch die kleinere und betrachtet den Rest (Modulo-Rechnung).
Das ganze wiederholt man solange bis der Rest 0 ergibt. Jedoch wird nach jeder Berechnung der Wert von Zahl1 auf Zahl2 gesetzt und Zahl2 bekommt den Wert des Rests.
Sobald der Rest 0 ist, hat man den ggT bestimmt. Der ggT ist der letzte Rest der ungleich Null war.

Beispiel:

Zahl 1: 19, Zahl 2: 7

19 % 7 = 5
7 % 5 = 2
5 % 2 = 1
2 % 1 = 0

Der ggT entspricht dem letzten Rest der ungleich Null war. Der größte gemeinsame Teiler von 19 und 5 ist also 1.

ggT Bestimmung durch Primfaktorzerlegung

Eine andere Möglichkeit der Bestimmung des ggT ist die Primfaktorzerlegung.
Dazu zerlegt man beide Zahlen in ihre Primfaktoren und die größte gemeinsame Zahl in beiden Primfaktorzerlegungen ist dann der ggT.
Auch wenn diese Methode scheinbar einfacher klingt, dauert die Primfaktorzerlegung oft sehr viel länger als die Ausführung des euklidische Algorithmus.

Beispiel:

Zahl 1: 1820, Zahl 2: 686

1820 = 2 * 2 * 5 * 7 * 13
686 = 2 * 7 * 7 * 7

Der ggT von 1820 und 686 ist also 7*2 = 14.