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.

Zuletzt aktualisiert: 2026-08-30

Zahl A

Zahl B

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.

Was die Berechnung von ggT und kgV ist

Der größte gemeinsame Teiler (ggT) ist die größte ganze Zahl, die zwei ganze Zahlen ohne Rest teilt, und das kleinste gemeinsame Vielfache (kgV) ist die kleinste ganze Zahl unter den gemeinsamen Vielfachen zweier ganzer Zahlen. Geben Sie zwei positive ganze Zahlen ein, und dieses Werkzeug ermittelt beide Werte augenblicklich mit dem euklidischen Algorithmus und zeigt zudem den Rechenweg Schritt für Schritt – Dividend, Divisor, Quotient und Rest.

Von Hand führt der übliche Weg über die Primfaktorzerlegung und das Suchen der gemeinsamen Faktoren, doch je größer die Zahlen werden, desto mühsamer wird eben diese Zerlegung. Der euklidische Algorithmus, den dieses Werkzeug verwendet, findet den größten gemeinsamen Teiler allein durch wiederholtes Dividieren, sodass auch Zahlen mit vielen Stellen genau dasselbe Verfahren durchlaufen. Die Eingabe ist auf ganze Zahlen ab 1 beschränkt; bei null, einer negativen Zahl oder einer Dezimalzahl wird kein Ergebnis angezeigt.

So verwenden Sie den ggT- und kgV-Rechner

Zahl A eingeben Tippen Sie die erste positive ganze Zahl ein, deren größten gemeinsamen Teiler und kleinstes gemeinsames Vielfaches Sie suchen.
Zahl B eingeben Tippen Sie die zweite positive ganze Zahl ein. Welche von A und B die größere ist, ändert am Ergebnis nichts.
Ergebnis prüfen Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) erscheinen automatisch.
Rechenweg nachvollziehen Jeder Schritt des euklidischen Algorithmus (Dividend = Divisor × Quotient + Rest) steht als Tabelle da, sodass Sie das Verfahren verfolgen können, bis der Rest null erreicht.

Tipps für die Nutzung

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.

Wann die Berechnung von ggT und kgV nützt

Vorarbeit zum Kürzen eines Bruchs

Ermitteln Sie den größten gemeinsamen Teiler von Zähler und Nenner, und beide dadurch zu teilen kürzt den Bruch. Wollen Sie das gekürzte Ergebnis selbst sehen, ist ein Bruchrechner mit Kürzungsfunktion praktisch.

Ausrechnen, wann mehrere Zyklen zusammenfallen

Geschieht das eine alle 3 Tage und das andere alle 5, fällt beides erst 15 Tage später wieder auf denselben Tag – das kleinste gemeinsame Vielfache von 3 und 5. Das lässt sich auf Schicht- und Veranstaltungszyklen übertragen.

Mathe-Hausaufgaben und Prüfungsübungen nachrechnen

Sie können sofort überprüfen, ob der von Hand ermittelte größte gemeinsame Teiler oder das kleinste gemeinsame Vielfache stimmt, Rechenweg inbegriffen.

Den Hauptnenner vorbereiten

Wenn Sie mehrere Brüche mit verschiedenen Nennern gleichnamig machen, wird das kleinste gemeinsame Vielfache dieser Nenner zum neuen gemeinsamen Nenner.

Die Grundlagen hinter der Kryptografie erfassen

Das Berechnen größter gemeinsamer Teiler trägt die moderne Kryptografie, unter anderem die RSA-Schlüsselerzeugung, sodass das Verfolgen des Rechenwegs ein nützlicher erster Schritt zum Verständnis ist.

Verwendete Begriffe

Größter gemeinsamer Teiler (ggT): Die größte unter den ganzen Zahlen, die zwei oder mehr ganze Zahlen ohne Rest teilen und ihre gemeinsamen Teiler heißen.
Kleinstes gemeinsames Vielfaches (kgV): Das kleinste unter den Vielfachen, die zwei oder mehr ganze Zahlen gemeinsam haben und ihre gemeinsamen Vielfachen heißen.
Euklidischer Algorithmus: Ein Verfahren, das den Rest der Division der größeren durch die kleinere Zahl betrachtet und dieselbe Rechnung mit dem Paar aus Divisor und Rest wiederholt, um den größten gemeinsamen Teiler zu finden. Sein Name geht auf das Werk des altgriechischen Mathematikers Euklid zurück.
Teilerfremd: Gesagt von zwei ganzen Zahlen, deren größter gemeinsamer Teiler 1 ist. Das kleinste gemeinsame Vielfache zweier teilerfremder Zahlen ist schlicht ihr Produkt.
Primfaktorzerlegung: Das Zerlegen einer ganzen Zahl in ein Produkt von Primzahlen. Größte gemeinsame Teiler und kleinste gemeinsame Vielfache lassen sich auch aus der Kombination gemeinsamer Primfaktoren gewinnen, doch bei großen Zahlen ist der euklidische Algorithmus schneller.
Gemeinsamer Teiler und gemeinsames Vielfaches: Ein gemeinsamer Teiler ist ein Teiler, den mehrere ganze Zahlen teilen; ein gemeinsames Vielfaches ist ein Vielfaches, das sie gemeinsam haben. Der ggT und das kgV sind das größte beziehungsweise kleinste davon.

Häufig gestellte Fragen

Der ggT ist die größte ganze Zahl, die beide Zahlen ohne Rest teilt, während das kgV die kleinste Zahl ist, die ein Vielfaches beider ist. Für 12 und 18 zum Beispiel ist der ggT 6 und das kgV 36.

Die Berechnung des ggT über die Primfaktorzerlegung wird mit wachsenden Zahlen langsamer, da die Zerlegung selbst aufwendiger wird. Der euklidische Algorithmus dagegen benötigt nur wiederholte Divisionen und Restberechnungen, sodass er den ggT selbst sehr großer ganzer Zahlen schnell findet.

Dieses Tool unterstützt nur positive ganze Zahlen. Geben Sie 0, eine negative Zahl oder eine Dezimalzahl ein, wird kein Ergebnis angezeigt.

Dieses Tool arbeitet mit jeweils zwei Zahlen. Bei drei oder mehr Zahlen können Sie es paarweise anwenden (z. B. zuerst den ggT von A und B bestimmen, dann den ggT dieses Ergebnisses mit C), um dasselbe Ergebnis zu erhalten.

Ü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.

Alle Wissenstexte ansehen