ggT- & kgV-Rechner
Geben Sie zwei positive ganze Zahlen ein, um mit dem euklidischen Algorithmus den größten gemeinsamen Teiler (ggT) zu finden – mit Anzeige jedes einzelnen Rechenschritts. Das kleinste gemeinsame Vielfache (kgV) wird gleichzeitig berechnet.
| Größter gemeinsamer Teiler (ggT) | |
|---|---|
| Kleinstes gemeinsames Vielfaches (kgV) |
Schritte des euklidischen Algorithmus
| Formel |
|---|
| = × + |
Was ist der euklidische Algorithmus?
Der euklidische Algorithmus ist eine klassische Methode, um den größten gemeinsamen Teiler zweier ganzer Zahlen zu finden. Das Verfahren: Man nimmt den Rest der Division der größeren durch die kleinere Zahl und wiederholt dieselbe Operation mit dem Divisor und diesem Rest. Sobald der Rest 0 erreicht, ist der Divisor an dieser Stelle der größte gemeinsame Teiler. So lässt sich der ggT selbst sehr großer Zahlen in relativ wenigen Schritten präzise bestimmen. Er ist in Euklids "Elementen" aus der Zeit um 300 v. Chr. überliefert und gehört damit zu den ältesten heute noch genutzten Algorithmen.
Tipps
- Das kleinste gemeinsame Vielfache (kgV) lässt sich mit der Formel "A × B ÷ ggT" berechnen. Es wird häufig verwendet, um einen gemeinsamen Nenner für Brüche zu finden oder herauszufinden, wann sich mehrere Ereignisse mit unterschiedlichen Perioden wieder überschneiden.
- Sind zwei Zahlen teilerfremd (ihr ggT ist 1), entspricht ihr kgV einfach A × B.
- Ein praktischer Vorteil des euklidischen Algorithmus ist, dass er den ggT großer Zahlen schneller berechnen kann als der Weg über die Primfaktorzerlegung.
- Die Reihenfolge, in der Sie die beiden Zahlen eingeben, beeinflusst das Ergebnis nicht – die Berechnung beginnt automatisch mit der größeren der beiden Zahlen.
Häufig gestellte Fragen
Übrigens – warum ein 2000 Jahre alter Algorithmus noch täglich im Einsatz ist
Der euklidische Algorithmus findet sich in Buch VII von Euklids "Elementen", verfasst vom griechischen Mathematiker um 300 v. Chr. Er gilt als einer der ältesten überlieferten Algorithmen und wird auch mehr als zweitausend Jahre später noch als einer der ersten Algorithmen in Informatik-Lehrbüchern vorgestellt.
Der Grund für diese lange Lebensdauer liegt in seiner rechnerischen Effizienz. Mathematisch ist bewiesen, dass die Anzahl der Schritte, die der euklidische Algorithmus benötigt, in etwa proportional zur Ziffernanzahl der Eingabe ist (der schlechteste Fall tritt bei Zahlenpaaren auf, die mit der Fibonacci-Folge zusammenhängen) – er kann den ggT selbst riesiger ganzer Zahlen in praktikabler Zeit finden.
Auch die moderne Kryptografie – etwa die RSA-Verschlüsselung – nutzt bei der Schlüsselerzeugung weiterhin die ggT-Berechnung (bzw. deren erweiterte Form, den erweiterten euklidischen Algorithmus). Es ist ein eindrucksvolles Beispiel für die Universalität der Mathematik, dass eine antike Entdeckung einen Teil der Technologie stützt, die heute das Internet absichert.