ggT- & kgV-Rechner
Ermitteln Sie den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache von zwei ganzen Zahlen oder einer ganzen Liste — mit dem euklidischen Algorithmus Schritt für Schritt, Primfaktorzerlegungen, einem Test auf Teilerfremdheit und der Bézout-Identität.
Verfasst von Suhaib Hassan. Die Algorithmen stammen von Euklid, und jedes Rechenbeispiel wird von Hand neu hergeleitet. Unsere Methodik.
Er führt den euklidischen Divisionsalgorithmus mit Ganzzahlen beliebiger Größe aus, gewinnt dann das kgV aus ggT(a, b) · kgV(a, b) = |a · b| und die Bézout-Koeffizienten aus dem erweiterten Algorithmus.
Er zeigt den schnellen Weg (Euklid) und den anschaulichen (gemeinsame Primfaktoren) nebeneinander, sodass sich beide gegenseitig überprüfen lassen.
—
Gemeinsame und getrennte Primfaktoren
Die Schnittmenge multipliziert sich zum ggT; alles zusammen multipliziert sich zum kgV.
Euklidischer Algorithmus
—
| Schritt | Division | Quotient | Rest |
|---|
Rechenweg Schritt für Schritt
—
Wichtige Identitäten
Zentrale Ergebnisse zu größten gemeinsamen Teilern und kleinsten gemeinsamen Vielfachen.
| Gleichung | Aussage | Hinweis |
|---|---|---|
| Euklidischer Algorithmus | ggT(a, b) = ggT(b, a mod b) | Höchstens etwa das 5-Fache der Stellenzahl der kleineren Zahl an Schritten |
| Bézout-Identität | ax + by = ggT(a, b) | Lösungen x, y existieren über den ganzen Zahlen immer |
| Produktdualität | ggT(a, b) · kgV(a, b) = |a · b| | Gilt für zwei Zahlen, nicht für drei oder mehr |
| Primexponenten | min(eₐ, e_b) für den ggT, max für das kgV | Exponenten jeder Primzahl vergleichen |
| Assoziativität | ggT(a, b, c) = ggT(ggT(a, b), c) | Eine Liste paarweise reduzieren |
| Teilerfremd | ggT(a, b) = 1 | Kein gemeinsamer Primfaktor |
Rechenbeispiele
Einen Boden fliesen
Welche größte quadratische Fliese deckt einen 12 × 18 großen Boden genau ab?
Die Fliesen sind 6 × 6, und (12 ÷ 6) × (18 ÷ 6) = 6 Fliesen
Busfahrplan
Zwei Linien fahren alle 12 bzw. alle 18 Minuten an einer Haltestelle ab. Wann fahren sie wieder gleichzeitig ab?
Zahnradzähne
Zahnräder mit 19 und 30 Zähnen sind teilerfremd. Wie lange dauert es, bis dieselben Zähne wieder aufeinandertreffen?
kgV = 19 × 30 = 570 Zähne — jeder Zahn trifft jeden anderen Zahn, sodass sich der Verschleiß gleichmäßig verteilt
Was sind ggT und kgV?
Der größte gemeinsame Teiler (ggT) zweier ganzer Zahlen ist die größte ganze Zahl, die beide teilt. Das kleinste gemeinsame Vielfache (kgV) ist die kleinste positive ganze Zahl, die durch beide teilbar ist. Sie werden zum Kürzen von Brüchen, zum Addieren von Brüchen (das kgV der Nenner) und zum Synchronisieren sich wiederholender Zyklen verwendet.
Zwei Methoden
- Primfaktorzerlegung: Schreiben Sie jede Zahl als Produkt von Primzahlen. Der ggT nimmt den kleinsten Exponenten jeder gemeinsamen Primzahl; das kgV nimmt den größten Exponenten jeder vorhandenen Primzahl.
- Euklidischer Algorithmus: Ersetzen Sie (a, b) wiederholt durch (b, a mod b), bis der Rest 0 ist; der letzte von null verschiedene Rest ist der ggT. Bei großen Zahlen ist er weit schneller, weil er nie faktorisieren muss.
Von Suhaib Hassan · Geprüft am 28. September 2026 · So überprüft CalculatePilot Formeln →
Quellen
- Euklid, Elemente, Buch VII, Propositionen 1–2, und Buch X — der euklidische Divisionsalgorithmus.
- Gauß, C. F. (1801). Disquisitiones Arithmeticae. Leipzig — eindeutige Primfaktorzerlegung.
- Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2, 3. Aufl., Abschnitt 4.5.2 (der größte gemeinsame Teiler).
- ISO 80000-2:2019, Quantities and units — Part 2: Mathematics.
Häufig gestellte Fragen
Gilt ggT(a, b) · kgV(a, b) = a · b auch für drei oder mehr Zahlen?
Nein. Die Produktidentität gilt nur für zwei Zahlen. Bei einer Liste berechnen Sie den ggT, indem Sie wiederholt den ggT des laufenden Ergebnisses mit der nächsten Zahl bilden, und das kgV entsprechend. Für 4, 6 und 10: ggT = 2 und kgV = 60, aber 2 × 60 = 120, während 4 × 6 × 10 = 240.
Was passiert, wenn eine oder beide Eingaben null sind?
ggT(a, 0) = |a|, weil jede Zahl 0 teilt. ggT(0, 0) ist per Konvention 0. Das kgV mit 0 ist per Konvention 0. Negative Eingaben liefern dieselben Ergebnisse wie ihre Beträge.
Warum ist der euklidische Algorithmus so viel schneller als die Faktorisierung?
Jede Division halbiert die größere Zahl mindestens alle zwei Schritte, daher braucht er höchstens etwa log₂(min(a, b)) × 2 Schritte. Für das Zerlegen großer Zahlen ist kein vergleichbar schnelles Verfahren bekannt, weshalb die RSA-Kryptografie darauf setzt, dass es schwer ist.
Wofür wird die Bézout-Identität verwendet?
Sie garantiert ganze Zahlen x und y mit ax + by = ggT(a, b). Ist ggT(a, b) = 1, so ist x das modulare Inverse von a modulo b — so berechnet RSA einen privaten Schlüssel aus einem öffentlichen Exponenten.
Wie kürze ich einen Bruch mit dem ggT?
Teilen Sie Zähler und Nenner durch ihren ggT. Für 48/180 ist ggT = 12, also 48/180 = 4/15. Ist der ggT 1, ist der Bruch bereits vollständig gekürzt.
Was bedeutet „teilerfremd“?
Zwei ganze Zahlen sind teilerfremd, wenn ihr einziger gemeinsamer positiver Teiler 1 ist, d. h. ggT = 1. Sie müssen selbst keine Primzahlen sein: 8 und 15 sind teilerfremd. Eine Menge ist paarweise teilerfremd, wenn jedes Paar darin teilerfremd ist.
Verwandte Rechner
Weiter mit Zahlentheorie.