Javascript
 

 ggT berechnen

Auf dieser Seite können Sie den größten gemeinsamen Teiler zweier Zahlen berechnen lassen:

Zahl 1:    ggT:
Zahl 2:    kgV:

Beschreibung

Das Programm berechnet den größten gemeinsamen Teiler (ggT) zweier Zahlen mit Hilfe des bereits von Euklid gefundenen Algorithmus:
Die größere Zahl wird so lange von der kleineren abgezogen, bis der verbleibende Rest kleiner ist als die abgezogene Zahl.
(Das entspricht einer sog. Modulo-Division, deren Ergebnis der Rest einer ganzzahligen Division ist.
Dafür gibt es in Javascript den Operator "%": 5 % 3 = 2, weil 5 / 3 = 1 Rest 2 ist.)
Das selbe macht man dann mit dem Rest bei der kleineren eingegebenen Zahl. Bleibt wieder ein Rest übrig, so wird der zweite Rest vom ersten abgezogen usw.
Es werden also immer wieder die Operanden vertauscht, und zwar so lange, bis sich der Rest Null ergibt. Der letzte Rest, mit dem das erreicht wird, ist der größte gemeinsame Teiler der beiden Zahlen, mit denen der Algorithmus begonnen wurde.
Der Algorithmus endet auch bei Eingabe von zwei Primzahlen, weil auch diese einen größten gemeinsamen Teiler haben, nämlich 1.
Da der Algorithmus einen Operandentausch beinhaltet, ist es unerheblich, ob zuerst die kleinere oder zuerst die größere Zahl eingegeben wird:
Das Ergebnis der Modulo-Division ist nämlich der Divisor selbst, wenn dieser größer ist als der Dividend. Genau in diesem Fall werden im Euklid-Algorithmus die Operanden getauscht.

Das kleinste gemeinsame Vielfache (kgV) errechnet sich als Produkt der beiden Zahlen dividiert durch ihren ggT.
Das wird anschaulich klar, wenn man sich die Bestimmung von kgV und ggT anhand der Primfaktorzerlegung ansieht, wie es in der Wikipedia erklärt wird. Dort finden sich auch weitere interessante Eigenschaften und Anwendungen von ggT und kgV!




Home
Falls diese Seite ohne Navigationsleiste angezeigt wird, aktivieren Sie Javascript oder klicken Sie hier!