Leitfaden: größter gemeinsamer Teiler (ggT)
What is GCD?
Der größte gemeinsame Teiler (ggT) ist die größte ganze Zahl, die zwei oder mehr ganze Zahlen ohne Rest teilt. Zum Beispiel ist ggT(48, 18) = 6, denn 6 ist die größte Zahl, die sowohl 48 als auch 18 restlos teilt. Der ggT ist ein grundlegender Begriff der Zahlentheorie und der Kryptografie.
Euclidean Algorithm
The oldest and most efficient method for calculating GCD is the Euclidean algorithm. It relies on repeated division: GCD(a, b) = GCD(b, a mod b), until b equals 0. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. This algorithm is extremely fast and works even for very large numbers.
Properties of GCD
ggT(a, b) * kgV(a, b) = a * b (das Produkt aus ggT und kgV entspricht dem Produkt der Zahlen). Ist ggT(a, b) = 1, sind a und b teilerfremd. Der ggT ist stets kleiner oder gleich der kleineren der beiden Zahlen. ggT(0, a) = |a| für jede Zahl a ungleich null.
Practical Applications
Der ggT dient zum Kürzen von Brüchen: Zähler und Nenner werden durch den ggT geteilt, um einen vollständig gekürzten Bruch zu erhalten. In der RSA-Kryptografie wird der ggT bei der Schlüsselerzeugung verwendet. In der Informatik bestimmt er die größte gemeinsame Aufteilung von Speicher- oder Prozessorressourcen. In der Musik lassen sich damit gemeinsame Intervalle für Rhythmen bestimmen.
Euklid findet den Teiler zweier neunstelliger Zahlen in drei Schritten
Herauszufinden, was zwei Zahlen gemeinsam haben, sieht nach Faktorisieren aus, und Faktorisieren ist langsam. Der euklidische Algorithmus umgeht es vollständig: ggT(123456789, 987654321) = 9, erreicht in drei Divisionen. Probedivision der kleineren Zahl hätte bis zu 11.111 Prüfungen gebraucht. Der Algorithmus ist über zweitausend Jahre alt und immer noch der, den jeder Computer verwendet.
So wird gerechnet
- Findet den größten gemeinsamen Teiler zweier oder mehrerer Zahlen mit dem euklidischen Algorithmus.
- Kürzt Brüche vollständig, was dieselbe Operation in anderer Kleidung ist.
- Nennt die Schrittzahl, denn die Geschwindigkeit ist der ganze Punkt.
ggT(a, b) = ggT(b, a mod b), wiederholt bis b = 0 das verbleibende a ist die Antwort vollständig gekürzt: a/b geteilt durch ggT(a, b) in beiden Teilen teilerfremd bedeutet ggT = 1 — überhaupt kein gemeinsamer Faktor
Rechenbeispiel
Euklid bei zunehmend garstigen Eingaben.
- ggT(1071, 462) = 21 in 3 Schritten
- ggT(123456789, 987654321) = 9 in 3 Schritten
- ggT(2⁴⁰, 3²⁰) = 1 in 15 Schritten
- ggT(832040, 514229) = 1 in 28 Schritten
- das letzte Paar sind aufeinanderfolgende Fibonacci-Zahlen — der schlechteste existierende Fall
Zwei neunstellige Zahlen lösen sich in drei Divisionen. Selbst die absichtlich schlechteste Eingabe, ein Paar aufeinanderfolgender Fibonacci-Zahlen, braucht 28. Die Schrittzahl wächst mit der Stellenzahl, nicht mit der Größe der Zahlen, weshalb der Algorithmus bis zu Werten mit Hunderten von Stellen skaliert.
Das Ergebnis lesen
- Aufeinanderfolgende Fibonacci-Zahlen sind der bewiesene schlechteste Fall, und zwar genau deshalb, weil jede Division so wenig wie möglich entfernt. ggT(987, 610) braucht 14 Schritte und ggT(75025, 46368) 23 — die Zahl kriecht hoch, während die Werte explodieren.
- Einen Bruch zu kürzen ist ein verkleideter ggT. 84/126 teilt den Teiler 42 und fällt in einem Schritt auf 2/3; der ggT ist genau die Grenze, bis zu der sich ein Bruch vereinfachen lässt, und durch etwas Kleineres zu teilen lässt Arbeit liegen.
- Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches sind zwei Hälften eines Werkzeugs, verbunden durch ggT(a,b) × kgV(a,b) = a × b. Hat man eines, liefert eine Multiplikation und eine Division das andere.
- Der euklidische Algorithmus trägt über seine erweiterte Form die moderne Kryptografie, die auch die Koeffizienten für modulare Inverse liefert. Die RSA-Schlüsselerzeugung hängt davon ab — ein langes Nachleben für ein Verfahren, das um 300 v. Chr. aufgeschrieben wurde.
Häufige Fragen
- Warum nicht einfach beide Zahlen faktorisieren?
- Weil Faktorisieren schwer ist und Euklid nicht. 123456789 in Primfaktoren zu zerlegen ist echte Arbeit; drei Reste zu nehmen nicht. Die Sicherheit von RSA beruht genau auf dieser Asymmetrie — Multiplikation und ggT sind billig, Faktorisieren ist es nicht.
- Was bedeutet ein ggT von 1?
- Die Zahlen sind teilerfremd — sie teilen keinen Faktor über 1. Es bedeutet nicht, dass eine von beiden prim ist: 8 und 9 sind teilerfremd und keine davon ist prim. Es bedeutet aber, dass der Bruch 8/9 bereits vollständig gekürzt ist.