Der größte gemeinsame Teiler (ggT) ist die jeweils größte natürliche Zahl , durch die sich zwei oder mehr gegebene ganze Zahlen ohne Rest teilen lassen. Weiterhin sind auch alle (echten) Teiler von dann Teiler aller beteiligten Zahlen, aber nicht die größten Teiler. Ist der größte gemeinsame Teiler , sind die beteiligten Zahlen teilerfremd. In der elementaren Mathematik ist dessen wichtigste Anwendung das Kürzen von Brüchen.
So ist der , da sich sowohl und durch teilen lassen. Der Bruch lässt sich zu kürzen. Die beiden „verbleibenden“ Zahlen und sind nun teilerfremd und lassen sich nicht weiter kürzen.
Sein Pendant ist das kleinste gemeinsame Vielfache (kgV). Beide spielen unter anderem in der Arithmetik, der Algebra und der Zahlentheorie eine Rolle.
Wichtigste Anwendung ist heutzutage die Kryptografie.
Das Konzept des größten gemeinsamen Teilers lässt sich auf Gaußsche Zahlen, Polynome und vieles andere erweitern.
Definition Der größte gemeinsame Teiler ggT zweier ganzen Zahlen und , von denen mindestens eine ungleich Null ist, ist die größte ganze Zahl , so dass ein Teiler sowohl von als auch von ist. Das heißt, es gibt ganze Zahlen und , so dass und ist und die größte Zahl mit dieser Eigenschaft ist.
Als Operator wird er in deutschsprachigen Texten, (greatest common divisor) in englischsprachigen Texten geschrieben, wobei letztere Schreibweise auch in deutschsprachigen Texten zu finden ist. Eine weitere Bezeichnung ist greatest common factor.
Ist eine der beiden Zahlen und Null, so ist der ggT der absolute Wert der betragsmäßig größeren Zahl: ,
da ist und was auch mit und übereinstimmt, wobei hier für für positive und für negative Zahlen steht. Dieser Fall ist weiterhin wichtig für den Abschluss des euklidischen Algorithmus.
Sind beide Zahlen Null, so ergibt letztere Regel ,
was wiederum mit und übereinstimmt, auch wenn die Zahl mit dem Begriff größter gemeinsamer Teiler nicht harmonisiert (obwohl es für den ggT gar keiner Division bedarf, siehe Definition).
Diese Definition bzw. Konvention wird meist auch verwendet, da sie einige Konzepte vereinfacht (wie z. B. die Bézout-Identität). Auch die meisten Computeralgebrasysteme, wie z. B. Wolfram Alpha benutzen diese Definition. Einige Autoren lassen jedoch ähnlich wie undefiniert.
Der ggT von und ist ihr größter gemeinsamer positiver Teiler in der Quasiordnung der Teilbarkeit. Das bedeutet, dass die gemeinsamen Teiler von und genau die Teiler ihres ggT sind. Dies wird in der Regel mit Hilfe des Lemma von Euklid, des Fundamentalsatzes der Arithmetik oder des euklidischen Algorithmus bewiesen. Dies ist die Bedeutung von „größte“, die für die Verallgemeinerung des Konzepts des ggT verwendet wird. Dies spielt eine wesentliche Rolle, wenn man die Schulmathematik verlässt und nicht nur Zahlen, sondern komplexere mathematische Konzepte wie Polynome, Funktionen und Matrizen verwendet.
Beispiele Größter gemeinsamer Teiler zweier Zahlen Wolfram Alpha zu ggT(12, 18) hat die Teiler: . hat die Teiler: . Die gemeinsamen Teiler von und sind: und . Der größte gemeinsame Teiler ist :
Größter gemeinsamer Teiler dreier Zahlen Wolfram Alpha zu ggT(12, 18, 30) hat die Teiler: . hat die Teiler: . hat die Teiler: . Die gemeinsamen Teiler von , und sind: und . Der größte gemeinsame Teiler ist :
Größter gemeinsamer Teiler zweier Polynome Die „Größe“ wird hier gemessen im Polynomgrad.
Im Ring : hat die Teiler , . Beide haben den Grad 1. hat den Teiler . Ergebnis: Der gradmäßig größte gemeinsame Teiler von und ist . .
Wolfram Alpha zu ggT(2x³ + 9x² + 6x + 1, 3x³ + 14x² + 11x + 2) hat die Teiler und . hat die Teiler und . lässt sich zwar darstellen als . Wegen ist es aber prim im Ring . Die gemeinsamen Teiler von und sind im Ring : und . Ergebnis: Der gradmäßig größte gemeinsame Teiler ist: .
Im Ring Die gemeinsamen Teiler von und sind wegen
, , und . Ergebnis: Der größte gemeinsame Teiler im Ring ist: .
Im Ring .
Rechenregeln für Zahlen Für ganze Zahlen und als dem Betrag von gilt: ● Kommutativgesetz ● Assoziativgesetz ● Distributivgesetz ● ● ● ● ● für ● ● mindestens für ● ● ● ● Verhältnis zwischen ggT und kgV ● Ist ein gemeinsamer Teiler von und , dann gilt: teilt und für ● Ist ( und sind kongruent modulo ), dann gilt:
Aus der genannten Rechenregel ergibt sich speziell . Dies ergibt sich auch daraus, dass jede ganze Zahl (sogar die 0 selbst) wegen Teiler der 0 ist, während umgekehrt 0 keine von 0 verschiedene Zahl teilt.
Hält man eines der beiden Argumente fest, dann ist eine multiplikative Funktion, denn für teilerfremde Zahlen und gilt:
Berechnung des größten gemeinsamen Teilers Berechnung mittels Primfaktorzerlegung Für die Berechnung mittels Primfaktorzerlegung zweier Zahlen und verwendet man alle Primfaktoren, die in jeder der beiden Zahlen vorkommen, mit der jeweils kleinsten vorkommenden Potenz.
Gegeben seien die Primfaktorzerlegungen:
mit resp. als den Exponenten des Primfaktors der Zahl resp. der Zahl (für Da beide, und , ganze Zahlen sind, sind alle diese Exponenten .
Der berechnet sich zu
mit als dem kleinsten Exponenten des Primfaktors beider Zahlen.
Beispiel Gesucht ist der größte gemeinsame Teiler von und .
Die beiden Primfaktorzerlegungen lauten:
Dabei sind die jeweils kleinsten Exponenten in Rot, die anderen (irrelevanten) in Grau gesetzt.
Die jeweils kleinsten Exponenten sind . Daher folgt:
Euklidischer Algorithmus
Die Berechnung der Primfaktorzerlegung großer Zahlen und damit auch die Bestimmung des größten gemeinsamen Teilers über die Primfaktorzerlegungen ist sehr aufwändig bis hin zu praktisch unmöglich. Allerdings benötigt man auch gar nicht die Primfaktoren der beteiligten Zahlen, um den ggT zu bestimmen. Mit dem euklidischen Algorithmus existiert ein effizientes Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen. So braucht man von und gar nicht die Primfaktoren zu kennen, um zu erkennen, dass der ist. Über die Primfaktoren-Zerlegung wäre das eine Lebensaufgabe, mit dem euklidischen Algorithmus ist das Ergebnis sofort zu sehen.
Der klassische euklidische Algorithmus (wie von Euklid vor 2300 Jahren beschrieben) berechnet den größten gemeinsamen Teiler, indem er nach einem gemeinsamen „Maß“ für die Längen zweier Linien sucht.Lambacher Schweizer: Mathematik für Gymnasien 5 Niedersachsen. Klett Verlag, Stuttgart 2006, ISBN 978-3-12-734551-3, S. 197. Dazu wird die kleinere zweier Längen von der größeren mehrfach abgezogen, bis ein Ergebnis übrig bleibt, das kleiner als die kleinere ist (erste zwei Schritte im Beispiel). Bei einer Differenz von 0 ist man fertig und die kleinere Länge das Ergebnis. Andernfalls wiederholt man dieses Abziehen – jetzt aber mit der kleineren Länge anstelle der größeren und der letzten Differenz anstelle der kleineren Länge (im Beispiel die Schritte drei bis sieben mit dem Rest 13 als der kleineren Länge und 65 als der jetzt größeren). Beispiel für den größten gemeinsamen Teiler von 143 und 65:
Der größte gemeinsame Teiler von 143 und 65 ist somit 13.
Beim modernen euklidischen Algorithmus wird in aufeinanderfolgenden Schritten jeweils eine Division mit Rest durchgeführt, wobei im nächsten Schritt der Divisor zum neuen Dividenden und der Rest zum neuen Divisor wird. Der Divisor, bei dem sich Rest 0 ergibt, ist der größte gemeinsame Teiler der Ausgangszahlen. Beispiel für die Ausgangszahlen 143 und 65:
Somit ist 13 der größte gemeinsame Teiler von 143 und 65.Schüler-Duden: Die Mathematik I. Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 100 Beide Verfahren sind auch kombinierbar, bei kleineren Unterschieden kann man Subtrahieren, bei größeren die Division/Modulo-Operation verwenden.
In der Programmiersprache C kann der Algorithmus für zwei vorzeichenlose 64-Bit-Ganzzahlen wie folgt formuliert werden:
#include <stdint.h>
uint64_t ggT_Div_Schleife (uint64_t a, uint64_t b) { if (a == 0) return b; if (b == 0) return a;
do { uint64_t h = a % b; a = b; b = h; } while (b != 0);
return a; }
Eine Variante mit Rekursion (genauer: Endrekursion) lässt sich so formulieren:
uint64_t ggT_Div_Rekursiv (uint64_t a, uint64_t b) { if (a == 0) return b; if (b == 0) return a; return ggT_Div_Rekursiv (b, a % b); }
Beide Versionen erzeugen mit Optimierung durch Auflösung der Endrekursion identischen Code.Compiler Explorer
Steinscher Algorithmus Neben dem euklidischen Algorithmus mit Modulo-Operation (bekanntere Version) und dem euklidischen Algorithmus mit rekursiver Subtraktion (ursprüngliche Version von Euklid) gibt es den steinschen Algorithmus als clevere Modifikation des euklidischen Algorithmus mit rekursiver Subtraktion.
Auf aktuellen CPUsC++, Microsoft Compiler, 64 bit-Code, Prozessoren um das Jahr 2020, Intel Cannon Lake, Raptor Lake, AMD ZEN 3, ZEN 4 läuft der steinsche Algorithmus etwa dreimal langsamer als der euklidische Algorithmus mit Modulo-Operation.
Er vermeidet Divisionen und erkauft sich das durch viele schlecht vorhersagbare Sprünge. Erstere sind auf aktuellen CPUs mittlerweile relativ schnell (64-Bit-Ganzzahl- wie auch -Gleitkomma-Division: 14 ± 1 Takte Latenz), letztere bremsen aktuelle CPUs massiv aus (falsch vorhergesagter Sprung: 18 ± 3 Straftakte Latenz).
Im Gegensatz zum euklidischen Algorithmus mit rekursiver Subtraktion zeigt er nicht dessen asymptotisch extrem lange Laufzeiten im Worst-Case-Fall, wenn irgendwann bei der rekursiven Berechnung Operanden mit sehr unterschiedlicher Größe entstehen (die zur quasi endlosen rekursiven Subtraktions-Schleifen führen, siehe Kommentare).
Der Knuth-Algorithmus ist der von Donald E. Knuth optimierte Algorithmus auf heutige CPUs angewendet.
Das gemessene Laufzeitverhalten zeigt die folgende Tabelle. Die verwendete Implementierung des ggT der Code darunter. Alle vier Implementierungen liefern die gleichen numerischen Ergebnisse für .
+ Ausführungszeiten in Nanosekunden für gleichverteilte Argumente (1 … 2n − 1)AMD Ryzen 9 3900X, Microsoft VC 2022, Optionen /GL /O2Compiler Explorer Zahlen-paare ggT(64 bit, 64 bit) ggT(64 bit, 48 bit) ggT(64 bit, 32 bit) Euklid(Div) Knuth Stein Euklid(Sub) Euklid(Div) Knuth Stein Euklid(Sub) Euklid(Div) Knuth Stein Euklid(Sub) 103 142 122 462 591 111 113 345 307 · 103 76 105 317 5,0 · 109 104 142 122 387 1024 111 113 352 495 · 103 78 105 322 11,9 · 109 105 142 122 382 800 111 113 348 729 · 103 78 106 322 zu lang*) 106 142 122 379 843 111 114 351 520 · 103 78 106 325 zu lang*) 107 142 122 380 1754 111 113 336 zu lang*) 78 106 322 zu lang*) *) Messung abgebrochen, da Ausführungsdauer zu lang
#include <cstdint> #include <bit> // für std::countr_zero #include <algorithm> // für std::swap
using u64 = uint64_t;
// Steinscher Algorithmus u64 Stein(u64 a, u64 b) { if (b==0) return a; if (b&1) return a <= b ? Stein(a, b-a) : Stein(b, a-b); return a&1 ? Stein(a, b>>1) : Stein(a>>1, b>>1)<<1; }
// Klassischer Euklidscher Algorithmus mit Subtraktion u64 Euklid_Sub(u64 a, u64 b) { while (a != b) if (a > b) a -= b; // Wenn a ≫ b oder a ≪ b, dauert diese Ausführung längere Zeit. else b -= a; // Im schlimmsten Fall (UINT64_MAX, 1) mehrere hundert Jahre. return a; }
// Euklidscher Algorithmus mit Division u64 Euklid_Div(u64 a, u64 b) { return b ? Euklid_Div(b, a % b) : a; }
// Hilfsfunktion für Steinscher Algorithmus nach D. E. Knuth (für ab Mitte der 1980er Jahre entwickelte CPU EIN Maschinenbefehl) unsigned long CountZeros(u64 x) // liefert für x>0 die Position des niedrigsten gesetzten Bits, für x=0 ist das Verhalten irrelevant { // return std::countr_zero(x); // ab C++20 // unsigned long ret; ::_BitScanForward64 (& ret, x); return ret;// für Microsoft VS return __builtin_ffsll(x) - 1; // für GnuC, Clang, ellcc, Intel icc, nvc, zigC++ }
// Steinscher Algorithmus nach D. E. Knuth u64 Knuth(u64 a, u64 b) { if (a == 0 || b == 0) // falls eines oder beide Argumente 0 sind, return a | b; // ist das andere Argument oder 0 das Ergebnis