ggT & kgV Rechner: Euklidischer Algorithmus, teilerfremd

Berechne ggT und kgV zweier oder mehrerer Ganzzahlen mit dem euklidischen Algorithmus, der Bézout-Identität, Primfaktorzerlegung und Teilerfremdheitstest.

Berechnungsparameter
War dieser Rechner nützlich?

Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches

Der größte gemeinsame Teiler ggT(a, b) zweier nicht beide null Ganzzahlen ist die größte positive Ganzzahl, die sowohl a als auch b ohne Rest teilt. Das kleinste gemeinsame Vielfache kgV(a, b) ist die kleinste positive Ganzzahl, die Vielfaches beider ist. Konvention: ggT(0, 0) = 0 und kgV(0, x) = 0. Für beliebige Ganzzahlen gilt die Grundidentität ggT(a, b) · kgV(a, b) = |a · b|.

Euklidischer Algorithmus

Der euklidische Algorithmus, beschrieben in Euklids Elementen (Buch VII, ca. 300 v. Chr.), berechnet ggT(a, b) durch fortgesetzte Division: ggT(a, b) = ggT(b, a mod b), bis ggT(x, 0) = |x|. Beispiel: ggT(252, 105) = ggT(105, 42) = ggT(42, 21) = ggT(21, 0) = 21. Terminiert in O(log(min(a, b))) Schritten; der schlechteste Fall steht in Verbindung mit der Fibonacci-Folge.

Erweiterter Algorithmus und Bézout-Identität

Der erweiterte euklidische Algorithmus liefert neben ggT(a, b) = d auch Ganzzahlen s, t mit d = a · s + b · t (Bézout-Identität). Essenziell in der Kryptographie (RSA, modulares Inverses) und zum Lösen linearer diophantischer Gleichungen ax + by = c (lösbar genau dann, wenn ggT(a, b) | c).

kgV-Formel

kgV(a, b) = |a · b| / ggT(a, b). Beispiel: kgV(12, 18) = 216 / 6 = 36. Für mehrere Zahlen rekursiv: kgV(a, b, c) = kgV(kgV(a, b), c).

Primfaktorzerlegung

Wenn a = ∏ pᵢ^αᵢ und b = ∏ pᵢ^βᵢ, dann ggT = ∏ pᵢ^min(αᵢ, βᵢ) und kgV = ∏ pᵢ^max(αᵢ, βᵢ). Anschaulich, aber ineffizient bei großen Zahlen: Faktorisierung ist ein schweres Problem, Grundlage von RSA.

Teilerfremd

Zwei Ganzzahlen heißen teilerfremd, wenn ggT = 1. Voraussetzung für den chinesischen Restsatz und die Existenz des modularen Inversen a⁻¹ mod n. Beispiele: (8, 15), (9, 28).

Eigenschaften

  • Kommutativ: ggT(a, b) = ggT(b, a).
  • Assoziativ: ggT(ggT(a, b), c) = ggT(a, ggT(b, c)).
  • ggT(a, 0) = |a|; ggT(a, 1) = 1.
  • p/q vollständig gekürzt ⇔ ggT(p, q) = 1.

Bedienung

Gib zwei oder mehr Ganzzahlen kommagetrennt ein (z. B. 12, 18, 24). Der Rechner liefert ggT, kgV, Euklid-Schritte, Bézout-Koeffizienten s, t (zwei Eingaben), Primfaktorzerlegung und Teilerfremdheitstest.

Anwendungen

Bruchkürzung, Synchronisation periodischer Ereignisse, Kryptographie (RSA, ElGamal), Prozessplanung, Musiktheorie (harmonische Verhältnisse).

Ein 2300 Jahre alter Algorithmus

Der euklidische Algorithmus steht im VII. Buch der Elemente (um 300 v. Chr.) und gilt als der älteste nicht-triviale Algorithmus, der noch in Gebrauch ist. Seine Effizienz ist bemerkenswert: Die Schrittzahl übersteigt nie das Fünffache der Ziffernzahl der kleineren Zahl (Satz von Lamé, 1844), und der schlechteste Fall tritt bei zwei aufeinanderfolgenden Fibonacci-Zahlen ein. Donald Knuth nannte ihn den "Urahn aller Algorithmen". In der heutigen Technik wählt die RSA-Kryptographie Exponenten teilerfremd zur eulerschen Phi-Funktion und berechnet Inverse mit dem erweiterten Euklid, während Getriebe teilerfremde Zähnezahlen nutzen, um den Verschleiß gleichmäßig zu verteilen.

Aktualisiert im Juli 2026

Häufig gestellte Fragen

Wie funktioniert der euklidische Algorithmus?

Man teilt die größere Zahl durch die kleinere und ersetzt die größere durch den Rest, bis der Rest null ist: Der letzte von null verschiedene Divisor ist der ggT. Für 48 und 18: 48 = 18·2 + 12, dann 18 = 12·1 + 6, schließlich 12 = 6·2 + 0, also ggT = 6. Der Rechner zeigt jeden Divisionsschritt.

Wie hängen ggT und kgV zusammen?

Für zwei Zahlen gilt die Identität ggT(a,b) × kgV(a,b) = a × b. Mit 48 und 18: Der ggT ist 6, also kgV = 48·18/6 = 144. Der Rechner nutzt genau diese Identität, die aber nur für Paare gilt: Bei drei oder mehr Zahlen wird das Ergebnis paarweise über die gesamte Liste iteriert.

Was bedeutet teilerfremd?

Teilerfremd (koprim) heißt ggT = 1: Die Zahlen teilen keinen Primfaktor, wie 8 und 15. Sie müssen selbst keine Primzahlen sein: 8 = 2³ und 15 = 3·5 sind beide zusammengesetzt und dennoch teilerfremd. Teilerfremdheit liegt der eulerschen Phi-Funktion und der RSA-Kryptographie zugrunde.

Wozu dient das Lemma von Bézout?

Es garantiert ganze Zahlen x und y mit ax + by = ggT(a,b): Für 48 und 18 gilt 6 = 48·(−1) + 18·3. Der Rechner bestimmt sie mit dem erweiterten euklidischen Algorithmus. Damit berechnet man modulare Inverse — das Herzstück der modularen Arithmetik, fehlerkorrigierender Codes und der Public-Key-Kryptographie.

Wie berechnet man ggT und kgV über die Primfaktorzerlegung?

Man zerlegt die Zahlen: Der ggT nimmt die gemeinsamen Faktoren mit dem kleinsten Exponenten, das kgV alle Faktoren mit dem größten Exponenten. Für 48 = 2⁴·3 und 18 = 2·3²: ggT = 2·3 = 6 und kgV = 2⁴·3² = 144. Die Methode ist lehrreich, aber bei großen Zahlen langsam — dort bleibt Euklid unschlagbar.

Wofür braucht man das kgV in der Praxis?

Zum Addieren von Brüchen mit dem kleinsten gemeinsamen Nenner, zum Synchronisieren periodischer Ereignisse (zwei Busse im 12- und 18-Minuten-Takt treffen sich alle kgV = 36 Minuten) und zum Auslegen von Zahnrädern und Wartungszyklen. Der ggT kürzt dagegen Brüche und teilt Mengen in größtmögliche gleiche Teile.

Akzeptiert der Rechner mehr als zwei Zahlen?

Ja: Gib beliebig viele Zahlen ein, getrennt durch Komma, Leerzeichen oder Semikolon. ggT und kgV werden iterativ über die ganze Liste berechnet; die Euklid-Schritte und das Lemma von Bézout werden für das erste Paar angezeigt. Negative Vorzeichen werden ignoriert (Betrag jeder Zahl).

Kommentare (0)

Noch keine Kommentare. Sei der Erste!