Der größte gemeinsame Teiler ggT ist die jeweils größte natürliche Zahl m displaystyle m durch die sich zwei oder mehr g
Gekürzter Bruch

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
- 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
- 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 .
- .
- 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. 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. 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.
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 steinsche Algorithmus als clevere Modifikation des euklidischen Algorithmus mit rekursiver Subtraktion.
Auf aktuellen CPUs läuft der Steinsche Algorithmus etwa dreimal langsamer als euklidischen 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 .
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 unsigned long const zeros = CountZeros(a | b); // LSB-Nullen, werden einmalig bestimmt a >>= CountZeros(a); do { b >>= CountZeros(b); if (a > b) std::swap (a, b); // vertausche Variablen, damit immer die kleinere von der größeren Zahl abgezogen wird b -= a; } while (b); return a << zeros; }
Berechnung mittels Probieren
Die einfachste, aber meist langsamste Methode ist das Probieren:
- Beginnend von der kleinsten der Zahlen (daher sollte diese klein sein) wird abwärts zählend die Teilbarkeit geprüft.
- Teilbar durch 8? 8 ist teilbar, 12 ist nicht teilbar
- Teilbar durch 7? 8 ist nicht teilbar, 12 ist nicht teilbar
- Teilbar durch 6? 8 ist nicht teilbar, 12 ist teilbar
- Teilbar durch 5? 8 ist nicht teilbar, 12 ist nicht teilbar
- Teilbar durch 4? 8 ist teilbar, 12 ist teilbar
- Teilbar durch 6? 6 ist teilbar, 12 ist teilbar
- Teilbar durch 6? 6 ist teilbar, 93099 ist nicht teilbar, da ungerade
- Teilbar durch 5? 6 ist nicht teilbar, 93099 ist nicht teilbar, da nicht auf 0 oder 5 endend
- Teilbar durch 4? 6 ist nicht teilbar, 93099 ist nicht teilbar, da ungerade
- Teilbar durch 3? 6 ist teilbar, 93099 ist offensichtlich teilbar
Berechnung für mehrere Zahlen
Berechnung mittels Primfaktorzerlegung
Die Berechnung mittels Primfaktorzerlegung lässt nativ die Berechnung für eine beliebige Menge von Zahlen zu. Man verwendet alle Primfaktoren, die in jeder der Zahlen vorkommen, mit der jeweils kleinsten vorkommenden Potenz.
Gegeben seien die Primfaktorzerlegungen:
mit dem jeweiligen Exponenten des Primfaktors der Zahl ().
Der ggT berechnet sich zu (mit dem kleinsten Exponenten des Primfaktors aller Zahlen):
- .
- Beispiel
Gesucht ist der kleinste gemeinsame Teiler von und .
Die Primfaktorenzerlegung lautet, wobei die jeweils kleinsten Exponenten in Rot, die anderen (irrelevanten) in Grau gesetzt sind:
- ,
die kleinsten Exponenten sind . Daher folgt:
- Bemerkung
Bei Anwendung des jeweils größten Exponenten erhält man (analog) das kleinste gemeinsame Vielfache:
- ,
die größten Exponenten sind . Daher folgt:
Das Produkt aus und ist , das der drei Zahlen ist , womit man sieht, dass die Multiplikationsregel für und für mehr als zwei Zahlen nicht gilt.
Berechnung mittels Verkettung
Wie wir schon festgestellt haben, ist die Berechnung über die Primfaktorenzerlegung nicht die effizienteste Methode.
Die Berechnung des erfolgt durch Verkettung. Die Reihenfolge (sowohl kommutativ wie assoziativ) ist dabei irrelevant:
Für die Berechnung von berechnet man z. B. zuerst
- und im zweiten Schritt
- .
Der Hintergrund, warum das funktioniert, ist die Eigenschaft des Minimum-Operators:
- , der sich durch das Anwenden auf die Exponenten auf die durchschlägt:
- .
und bezeichnen hier jeweils nichtleere Mengen an ganzen Zahlen, d. h. man kann eine Menge in (sinnvollerweise, aber nicht notwendigerweise echte) nichtleere Teilemengen und mit zerlegen und dann die Operation rekursiv anwenden.
Dies rechtfertigt die Schreibweise .
- Bemerkung
Das Gleiche gilt für das kleinste gemeinsame Vielfache, nur dass hier das Minimum jeweils durch das Maximum (der Exponenten) ersetzt wird.
Berechnen für Polynome
Die Bestimmung des für Polynome läuft auf geschicktes Raten und Polynomdivisionen bzw. auf die Bestimmung der Nullstellen der Polynome hinaus.
Letzteres erfolgt folgendermaßen:
wobei die Menge aller paarweise identischen Nullstellen der beiden Polynome umfasst.
- Beispiel
- .
Die gemeinsamen Nullstellen sind die doppelte Nullstelle und die einfache Nullstelle , weiterhin ist das .
- .
Der rationale Bruch
lässt sich für kürzen zu:
Lemma von Bézout
Nach dem Lemma von Bézout lässt sich der größte gemeinsame Teiler zweier ganzer Zahlen und als Linearkombination von und mit ganzzahligen Koeffizienten darstellen:
- mit
Beispielsweise besitzt der größte gemeinsame Teiler von und die folgende Darstellung:
Die Koeffizienten und können mit dem erweiterten euklidischen Algorithmus berechnet werden.
Sonderfälle
Für gerades , ungerades sowie ganzes gilt:
Setzt man eine Primzahl aus zwei echten Summanden zusammen, gilt für diese stets Teilerfremdheit:
- Aus folgt .
Anwendungen
Kürzen von Brüchen
Beim Kürzen wird ein gemeinsamer Faktor von Zähler und Nenner eines Bruches entfernt, wobei sich der Wert des Bruches nicht ändert, z. B. . Kürzt man mit dem größten gemeinsamen Teiler von Zähler und Nenner, entsteht ein Bruch, der nicht weiter kürzbar ist. Zum Beispiel ist , also
Ein Bruch mit Zähler und Nenner , bei dem ist, ist nicht weiter kürzbar. Er wird voll gekürzt, in der Mathematik vollständig oder maximal gekürzter Bruch genannt. In der englischsprachigen Literatur wird er „Simplified fraction“ oder „Reduced fraction“ genannt.
Zusammenhang zwischen größtem gemeinsamen Teiler (ggT) und kleinstem gemeinsamen Vielfachen (kgV)
- Satz
- Beweis
- Nachweis für positive ganze Zahlen und , alle anderen Fälle lassen sich analog behandeln. Sei , dann ist auch Teiler des Produkts . Die Zahl enthalte dagegen alle Primfaktoren des Produkts , die nicht enthält. Betrachtet man, wie der aus der Primfaktordarstellung des Produkts aus und berechnet wird, dann folgt . Daraus ergibt sich die obige Gleichung.
Weitere algebraische Strukturen mit ggT
Der Begriff des baut auf dem Begriff der Teilbarkeit auf, wie er in Ringen definiert ist. Man beschränkt sich bei der Diskussion des auf nullteilerfreie Ringe, im kommutativen Fall sind das die Integritätsringe.
Ein Integritätsring, in dem je zwei Elemente einen besitzen, heißt oder ggT-Bereich. (In einem -Ring haben je zwei Elemente auch ein .)
Im Allgemeinen besitzen solche Ringe keine Halbordnung, die antisymmetrisch ist, wie die ganzen oder die natürlichen Zahlen eine haben. Häufig ist die Teilbarkeitsrelation, die eine Quasiordnung ist, die einzige Ordnungsrelation. Deshalb lässt sich der gegebenenfalls nicht mehr eindeutig als nicht-negativ normieren, sondern nur bis auf Assoziiertheit bestimmen. Zwei Elemente und sind assoziiert, in Zeichen , wenn es eine Einheit mit gibt.
Wir erweitern den Begriff des auf die Menge aller größten gemeinsamen Teiler der Elemente einer Teilmenge eines Ringes , formal:
- .
In Worten: Die Teiler von sind genau die Elemente aus , die alle Elemente aus teilen. Die sind untereinander assoziiert.
Polynomringe
Man kann den z. B. auch für Polynome bilden. Statt der Primfaktorzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren:
Autor: www.NiNa.Az
Veröffentlichungsdatum:
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele, Mobiltelefon, Mobil, Telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, komputer, Informationen zu Gekürzter Bruch, Was ist Gekürzter Bruch? Was bedeutet Gekürzter Bruch?
Der grosste gemeinsame Teiler ggT ist die jeweils grosste naturliche Zahl m displaystyle m durch die sich zwei oder mehr gegebene ganze Zahlen ohne Rest teilen lassen Weiterhin sind auch alle echten Teiler von m displaystyle m dann Teiler aller beteiligten Zahlen aber nicht die grossten Teiler Ist der grosste gemeinsame Teiler 1 displaystyle 1 sind die beteiligten Zahlen teilerfremd In der elementaren Mathematik ist dessen wichtigste Anwendung das Kurzen von Bruchen So ist der ggT 10 15 5 displaystyle operatorname ggT 10 15 5 da sich sowohl 10 displaystyle 10 und 15 displaystyle 15 durch 5 displaystyle 5 teilen lassen Der Bruch 1015 displaystyle tfrac 10 15 lasst sich zu 23 displaystyle tfrac 2 3 kurzen Die beiden verbleibenden Zahlen 2 displaystyle 2 und 3 displaystyle 3 sind nun teilerfremd und lassen sich nicht weiter kurzen 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 grossten gemeinsamen Teilers lasst sich auf Gausssche Zahlen Polynome und vieles andere erweitern DefinitionDer grosste gemeinsame Teiler ggT zweier ganzen Zahlen a displaystyle a und b displaystyle b von denen mindestens eine ungleich Null ist ist die grosste ganze Zahl m displaystyle m so dass m displaystyle m ein Teiler sowohl von a displaystyle a als auch von b displaystyle b ist Das heisst es gibt ganze Zahlen a displaystyle alpha und b displaystyle beta so dass a m a displaystyle a m cdot alpha quad und b m b displaystyle quad b m cdot beta ist und m displaystyle m die grosste Zahl mit dieser Eigenschaft ist Als Operator wird er ggT a b displaystyle operatorname ggT a b in deutschsprachigen Texten gcd a b displaystyle operatorname gcd a b 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 a displaystyle a und b displaystyle b Null so ist der ggT der absolute Wert der betragsmassig grosseren Zahl ggT 0 a max 0 a max 0 a a displaystyle operatorname ggT 0 a operatorname max 0 a operatorname max 0 a a da a 0 displaystyle a geq 0 ist und was auch mit 0 a 0 displaystyle 0 a cdot 0 und a a sgn a displaystyle a a cdot operatorname sgn a ubereinstimmt wobei sgn a displaystyle operatorname sgn a hier fur 1 displaystyle 1 fur positive und 1 displaystyle 1 fur negative Zahlen steht Dieser Fall ist weiterhin wichtig fur den Abschluss des euklidischen Algorithmus Sind beide Zahlen Null so ergibt letztere Regel ggT 0 0 max 0 0 max 0 0 0 displaystyle operatorname ggT 0 0 operatorname max 0 0 operatorname max 0 0 0 was wiederum mit 0 0 0 displaystyle 0 0 cdot 0 und 0 0 0 displaystyle 0 0 cdot 0 ubereinstimmt auch wenn die Zahl 0 displaystyle 0 mit dem Begriff grosster gemeinsamer Teiler nicht harmonisiert obwohl es fur 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 Bezout Identitat Auch die meisten Computeralgebrasysteme wie z B Wolfram Alpha benutzen diese Definition Einige Autoren lassen ggT 0 0 displaystyle operatorname ggT 0 0 jedoch ahnlich wie 00 displaystyle tfrac 0 0 undefiniert Der ggT von a displaystyle a und b displaystyle b ist ihr grosster gemeinsamer positiver Teiler in der Quasiordnung der Teilbarkeit Das bedeutet dass die gemeinsamen Teiler von a displaystyle a und b displaystyle b 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 grosste die fur die Verallgemeinerung des Konzepts des ggT verwendet wird Dies spielt eine wesentliche Rolle wenn man die Schulmathematik verlasst und nicht nur Zahlen sondern komplexere mathematische Konzepte wie Polynome Funktionen und Matrizen verwendet BeispieleGrosster gemeinsamer Teiler zweier Zahlen ggT 12 18 displaystyle operatorname ggT 12 18 12 displaystyle 12 hat die Teiler 1 2 3 4 6 12 displaystyle 1 2 3 4 6 12 18 displaystyle 18 hat die Teiler 1 2 3 6 9 18 displaystyle 1 2 3 6 9 18 Die gemeinsamen Teiler von 12 displaystyle 12 und 18 displaystyle 18 sind 1 2 3 displaystyle 1 2 3 und 6 displaystyle 6 Der grosste gemeinsame Teiler ist 6 displaystyle 6 ggT 12 18 6 displaystyle operatorname ggT 12 18 6 dd Grosster gemeinsamer Teiler dreier Zahlen ggT 12 18 30 displaystyle operatorname ggT 12 18 30 12 displaystyle 12 hat die Teiler 1 2 3 4 6 12 displaystyle 1 2 3 4 6 12 18 displaystyle 18 hat die Teiler 1 2 3 6 9 18 displaystyle 1 2 3 6 9 18 30 displaystyle 30 hat die Teiler 1 2 3 5 6 10 15 30 displaystyle 1 2 3 5 6 10 15 30 Die gemeinsamen Teiler von 12 displaystyle 12 18 displaystyle 18 und 30 displaystyle 30 sind 1 2 3 displaystyle 1 2 3 und 6 displaystyle 6 Der grosste gemeinsame Teiler ist 6 displaystyle 6 ggT 12 18 30 6 displaystyle operatorname ggT 12 18 30 6 dd Grosster gemeinsamer Teiler zweier Polynome Die Grosse wird hier gemessen im Polynomgrad Im Ring Z x displaystyle mathbb Z x ggT x2 1 x 1 displaystyle operatorname ggT x 2 1 x 1 x2 1 displaystyle x 2 1 hat die Teiler x 1 displaystyle x 1 x 1 displaystyle x 1 Beide haben den Grad 1 x 1 displaystyle x 1 hat den Teiler x 1 displaystyle x 1 Ergebnis Der gradmassig grosste gemeinsame Teiler von x2 1 displaystyle x 2 1 und x 1 displaystyle x 1 ist x 1 displaystyle x 1 ggT x2 1 x 1 x 1 displaystyle qquad qquad Longrightarrow operatorname ggT x 2 1 x 1 x 1 ggT 2x3 9x2 6x 1 3x3 14x2 11x 2 displaystyle operatorname ggT 2x 3 9x 2 6x 1 3x 3 14x 2 11x 2 2x3 9x2 6x 1 displaystyle 2x 3 9x 2 6x 1 hat die Teiler 2x 1 displaystyle 2x 1 und x2 4x 1 displaystyle x 2 4x 1 3x3 14x2 11x 2 displaystyle 3x 3 14x 2 11x 2 hat die Teiler 3x 2 displaystyle 3x 2 und x2 4x 1 displaystyle x 2 4x 1 x2 4x 1 displaystyle x 2 4x 1 lasst sich zwar darstellen als x 2 3 x 2 3 displaystyle x 2 sqrt 3 cdot x 2 sqrt 3 Wegen 3 Z displaystyle sqrt 3 notin mathbb Z ist es aber prim im Ring Z x displaystyle mathbb Z x Die gemeinsamen Teiler von 2x3 9x2 6x 1 displaystyle 2x 3 9x 2 6x 1 und 3x3 14x2 11x 2 displaystyle 3x 3 14x 2 11x 2 sind im Ring Z x displaystyle mathbb Z x 1 displaystyle 1 und x2 4x 1 displaystyle x 2 4x 1 dd dd Ergebnis Der gradmassig grosste gemeinsame Teiler ist x2 4x 1 displaystyle x 2 4x 1 ggT 2x3 9x2 6x 1 3x3 14x2 11x 2 x2 4x 1 displaystyle qquad qquad Longrightarrow operatorname ggT 2x 3 9x 2 6x 1 3x 3 14x 2 11x 2 x 2 4x 1 Im Ring Q 3 x displaystyle mathbb Q sqrt 3 x Die gemeinsamen Teiler von 2x3 9x2 6x 1 displaystyle 2x 3 9x 2 6x 1 und 3x3 14x2 11x 2 displaystyle 3x 3 14x 2 11x 2 sind wegen x2 4x 1 x 2 3 x 2 3 displaystyle x 2 4x 1 x 2 sqrt 3 cdot x 2 sqrt 3 1 displaystyle 1 x 2 3 displaystyle x 2 sqrt 3 x 2 3 displaystyle x 2 sqrt 3 und x2 4x 1 displaystyle x 2 4x 1 Ergebnis Der grosste gemeinsame Teiler im Ring Q 3 x displaystyle mathbb Q sqrt 3 x ist x2 4x 1 displaystyle x 2 4x 1 ggT 2x3 9x2 6x 1 3x3 14x2 11x 2 x2 4x 1 displaystyle qquad qquad Longrightarrow operatorname ggT 2x 3 9x 2 6x 1 3x 3 14x 2 11x 2 x 2 4x 1 Im Ring R x displaystyle mathbb R x ggT px2 p x 1 x 1 displaystyle operatorname ggT pi x 2 pi x 1 x 1 Rechenregeln fur ZahlenFur ganze Zahlen a b c k displaystyle a b c k und a displaystyle a als dem Betrag von a displaystyle a gilt ggT a b displaystyle operatorname ggT a b ggT b a displaystyle operatorname ggT b a Kommutativgesetz ggT a b c displaystyle operatorname ggT a b c ggT a ggT b c ggT ggT a b c displaystyle operatorname ggT a operatorname ggT b c operatorname ggT operatorname ggT a b c qquad Assoziativgesetz ggT k a k b displaystyle operatorname ggT k cdot a k cdot b k ggT a b displaystyle k cdot operatorname ggT a b Distributivgesetz ggT a b displaystyle operatorname ggT pm a pm b ggT a b displaystyle operatorname ggT a b ggT a 0 displaystyle operatorname ggT a 0 a displaystyle a ggT a 1 displaystyle operatorname ggT a 1 1 displaystyle 1 ggT a a displaystyle operatorname ggT a a a displaystyle a ggT a b displaystyle operatorname ggT a b ggT a bmoda ggT amodb b displaystyle operatorname ggT a b bmod a operatorname ggT a bmod b b fur a b 0 displaystyle a b neq 0 ggT a b ac displaystyle operatorname ggT a b ac ggT a b displaystyle operatorname ggT a b ggT a b displaystyle operatorname ggT a b ggT b a b displaystyle operatorname ggT b a b mindestens fur 0 a b displaystyle 0 leq a leq b ggT a displaystyle operatorname ggT a a displaystyle a ggT a b c displaystyle operatorname ggT a b c ldots ggT a ggT b c displaystyle operatorname ggT a operatorname ggT b c ldots ggT a1 an b1 bm displaystyle operatorname ggT a 1 ldots a n b 1 ldots b m ggT ggT a1 an ggT b1 bm displaystyle operatorname ggT operatorname ggT a 1 ldots a n operatorname ggT b 1 ldots b m ggT a b kgV a b displaystyle operatorname ggT a b cdot operatorname kgV a b ab displaystyle ab Verhaltnis zwischen ggT und kgV Ist k displaystyle k ein gemeinsamer Teiler von a displaystyle a und b displaystyle b dann gilt k displaystyle qquad k teilt ggT a b displaystyle operatorname ggT a b und ggT ak bk ggT a b k displaystyle qquad operatorname ggT Big tfrac a k tfrac b k Big qquad tfrac operatorname ggT a b k fur k 0 displaystyle k neq 0 Ist a b mod c displaystyle a equiv b bmod c a displaystyle a und b displaystyle b sind kongruent modulo c displaystyle c dann gilt ggT a c ggT b c displaystyle qquad operatorname ggT a c qquad quad operatorname ggT b c Aus der genannten Rechenregel ggT a 0 a displaystyle operatorname ggT a 0 a ergibt sich speziell ggT 0 0 0 displaystyle operatorname ggT 0 0 0 Dies ergibt sich auch daraus dass jede ganze Zahl a displaystyle a sogar die 0 selbst wegen a 0 0 displaystyle a cdot 0 0 Teiler der 0 ist wahrend umgekehrt 0 keine von 0 verschiedene Zahl teilt Halt man eines der beiden Argumente fest dann ist ggT displaystyle operatorname ggT eine multiplikative Funktion denn fur teilerfremde Zahlen a displaystyle a und b displaystyle b gilt ggT ab c ggT a c ggT b c displaystyle operatorname ggT ab c operatorname ggT a c cdot operatorname ggT b c Berechnung des grossten gemeinsamen TeilersBerechnung mittels Primfaktorzerlegung Fur die Berechnung mittels Primfaktorzerlegung zweier Zahlen a displaystyle a und b displaystyle b verwendet man alle Primfaktoren die in jeder der beiden Zahlen vorkommen mit der jeweils kleinsten vorkommenden Potenz Gegeben seien die Primfaktorzerlegungen a p1a1 p2a2 pmam displaystyle a p 1 alpha 1 cdot p 2 alpha 2 cdot cdots cdot p m alpha m b p1b1 p2b2 pmbm displaystyle b p 1 beta 1 cdot p 2 beta 2 cdot cdots cdot p m beta m mit aj displaystyle alpha j resp bj displaystyle beta j als den Exponenten des Primfaktors pj displaystyle p j der Zahl a displaystyle a resp der Zahl b displaystyle b fur j 1 m displaystyle j 1 ldots m Da beide a displaystyle a und b displaystyle b ganze Zahlen sind sind alle diese Exponenten 0 displaystyle geq 0 Der ggT a b displaystyle operatorname ggT a b berechnet sich zu ggT a b j 1mpjmin aj bj displaystyle operatorname ggT a b prod j 1 m p j min alpha j beta j mit min aj bj displaystyle min alpha j beta j als dem kleinsten Exponenten des Primfaktors pj displaystyle p j beider Zahlen Beispiel Gesucht ist der grosste gemeinsame Teiler von 2970 displaystyle 2970 und 12936 displaystyle 12 936 Die beiden Primfaktorzerlegungen lauten 2970 21 33 51 70 111 displaystyle 2970 2 color Red 1 cdot 3 color Gray 3 cdot 5 color Gray 1 cdot 7 color Red 0 cdot 11 color Red 1 12936 23 31 50 72 111 displaystyle 12 936 2 color Gray 3 cdot 3 color Red 1 cdot 5 color Red 0 cdot 7 color Gray 2 cdot 11 color Red 1 Dabei sind die jeweils kleinsten Exponenten in Rot die anderen irrelevanten in Grau gesetzt Die jeweils kleinsten Exponenten sind 1 1 0 0 1 displaystyle color Red 1 color Red 1 color Red 0 color Red 0 color Red 1 Daher folgt ggT 2970 12936 21 31 50 70 111 2 3 1 1 11 66 displaystyle operatorname ggT 2970 12 936 2 color Red 1 cdot 3 color Red 1 cdot 5 color Red 0 cdot 7 color Red 0 cdot 11 color Red 1 2 cdot 3 cdot 1 cdot 1 cdot 11 66 Euklidischer Algorithmus Hauptartikel Euklidischer Algorithmus Die Berechnung der Primfaktorzerlegung grosser Zahlen und damit auch die Bestimmung des grossten gemeinsamen Teilers uber die Primfaktorzerlegungen ist sehr aufwandig bis hin zu praktisch unmoglich Allerdings benotigt man auch gar nicht die Primfaktoren der beteiligten Zahlen um den ggT zu bestimmen Mit dem euklidischen Algorithmus existiert ein effizientes Verfahren um den grossten gemeinsamen Teiler zweier Zahlen zu berechnen So braucht man von 1000000004147 displaystyle 1 000 000 004 147 und 1000000004149 displaystyle 1 000 000 004 149 gar nicht die Primfaktoren zu kennen um zu erkennen dass der ggT 1000000004147 1000000004149 1 displaystyle operatorname ggT 1 000 000 004 147 1 000 000 004 149 1 ist Uber die Primfaktoren Zerlegung ware 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 grossten gemeinsamen Teiler indem er nach einem gemeinsamen Mass fur die Langen zweier Linien sucht Dazu wird die kleinere zweier Langen von der grosseren mehrfach abgezogen bis ein Ergebnis ubrig bleibt das kleiner als die kleinere ist erste zwei Schritte im Beispiel Bei einer Differenz von 0 ist man fertig und die kleinere Lange das Ergebnis Andernfalls wiederholt man dieses Abziehen jetzt aber mit der kleineren Lange anstelle der grosseren und der letzten Differenz anstelle der kleineren Lange im Beispiel die Schritte drei bis sieben mit dem Rest 13 als der kleineren Lange und 65 als der jetzt grosseren Beispiel fur den grossten gemeinsamen Teiler von 143 und 65 143 65 7878 65 13 Die entstandene Differenz 13 ist nun kleiner als der Subtrahend 65 die beiden Zahlen werden getauscht 65 13 5252 13 3939 13 2626 13 1313 13 0 Die entstandene Differenz ist 0 der letzte Minuend ist das Ergebnis displaystyle begin array rl l 143 65 amp 78 78 65 amp 13 amp scriptstyle text Die entstandene Differenz 13 ist nun kleiner als der Subtrahend 65 die beiden Zahlen werden getauscht 65 13 amp 52 52 13 amp 39 39 13 amp 26 26 13 amp 13 13 13 amp 0 amp scriptstyle text Die entstandene Differenz ist 0 der letzte Minuend ist das Ergebnis end array Der grosste gemeinsame Teiler von 143 und 65 ist somit 13 Beim modernen euklidischen Algorithmus wird in aufeinanderfolgenden Schritten jeweils eine Division mit Rest durchgefuhrt wobei im nachsten Schritt der Divisor zum neuen Dividenden und der Rest zum neuen Divisor wird Der Divisor bei dem sich Rest 0 ergibt ist der grosste gemeinsame Teiler der Ausgangszahlen Beispiel fur die Ausgangszahlen 143 und 65 143 65 2 Rest 13 65 13 5 Rest 0 Der letzte Divisor 13 ist das Ergebnis displaystyle begin array rl l 143 65 amp 2 amp scriptstyle text Rest 13 65 13 amp 5 amp scriptstyle text Rest 0 Der letzte Divisor 13 ist das Ergebnis end array Somit ist 13 der grosste gemeinsame Teiler von 143 und 65 Beide Verfahren sind auch kombinierbar bei kleineren Unterschieden kann man Subtrahieren bei grosseren die Division Modulo Operation verwenden In der Programmiersprache C kann der Algorithmus fur zwei vorzeichenlose 64 Bit Ganzzahlen wie folgt formuliert werden include lt stdint h gt 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 lasst 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 Auflosung der Endrekursion identischen Code Steinscher Algorithmus Neben dem euklidischen Algorithmus mit Modulo Operation bekanntere Version und dem euklidischen Algorithmus mit rekursiver Subtraktion ursprungliche Version von Euklid gibt es den steinsche Algorithmus als clevere Modifikation des euklidischen Algorithmus mit rekursiver Subtraktion Auf aktuellen CPUs lauft der Steinsche Algorithmus etwa dreimal langsamer als euklidischen Algorithmus mit Modulo Operation Er vermeidet Divisionen und erkauft sich das durch viele schlecht vorhersagbare Sprunge 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 Grosse entstehen die zur quasi endlosen rekursiven Subtraktions Schleifen fuhren 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 fur a b gt 0 displaystyle a b gt 0 Ausfuhrungszeiten in Nanosekunden fur gleichverteilte Argumente 1 2n 1 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 0 591 111 113 345 307 103 76 105 317 0 5 0 109104 142 122 387 1024 111 113 352 495 103 78 105 322 11 9 109105 142 122 382 0 800 111 113 348 729 103 78 106 322 zu lang 106 142 122 379 0 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 Ausfuhrungsdauer zu lang Quellcode fur die vier Implementierungen include lt cstdint gt include lt bit gt fur std countr zero include lt algorithm gt fur std swap using u64 uint64 t Steinscher Algorithmus u64 Stein u64 a u64 b if b 0 return a if b amp 1 return a lt b Stein a b a Stein b a b return a amp 1 Stein a b gt gt 1 Stein a gt gt 1 b gt gt 1 lt lt 1 Klassischer Euklidscher Algorithmus mit Subtraktion u64 Euklid Sub u64 a u64 b while a b if a gt b a b Wenn a b oder a b dauert diese Ausfuhrung langere 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 fur Steinscher Algorithmus nach D E Knuth fur ab Mitte der 1980er Jahre entwickelte CPU EIN Maschinenbefehl unsigned long CountZeros u64 x liefert fur x gt 0 die Position des niedrigsten gesetzten Bits fur x 0 ist das Verhalten irrelevant return std countr zero x ab C 20 unsigned long ret BitScanForward64 amp ret x return ret fur Microsoft VS return builtin ffsll x 1 fur 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 unsigned long const zeros CountZeros a b LSB Nullen werden einmalig bestimmt a gt gt CountZeros a do b gt gt CountZeros b if a gt b std swap a b vertausche Variablen damit immer die kleinere von der grosseren Zahl abgezogen wird b a while b return a lt lt zeros Berechnung mittels Probieren Die einfachste aber meist langsamste Methode ist das Probieren Beginnend von der kleinsten der Zahlen daher sollte diese klein sein wird abwarts zahlend die Teilbarkeit gepruft ggT 8 12 displaystyle operatorname ggT 8 12 Teilbar durch 8 8 ist nich teilbar 12 ist nicht teilbar Teilbar durch 7 8 ist nicht teilbar 12 ist nicht teilbar Teilbar durch 6 8 ist nicht teilbar 12 ist nich teilbar Teilbar durch 5 8 ist nicht teilbar 12 ist nicht teilbar Teilbar durch 4 8 ist nich teilbar 12 ist nich teilbar ggT 8 12 4 displaystyle quad longrightarrow operatorname ggT 8 12 4 ggT 6 12 displaystyle operatorname ggT 6 12 Teilbar durch 6 6 ist nich teilbar 12 ist nich teilbar ggT 6 12 6 displaystyle quad longrightarrow operatorname ggT 6 12 6 ggT 6 93099 displaystyle operatorname ggT 6 93 099 Teilbar durch 6 6 ist nich teilbar 93099 ist nicht teilbar da ungerade Teilbar durch 5 6 ist nicht teilbar 93099 ist nicht teilbar da nicht auf 0 oder 5 endend Teilbar durch 4 6 ist nicht teilbar 93099 ist nicht teilbar da ungerade Teilbar durch 3 6 ist nich teilbar 93099 ist offensichtlich teilbar ggT 6 93099 3 displaystyle quad longrightarrow operatorname ggT 6 93 099 3 Berechnung fur mehrere Zahlen Berechnung mittels Primfaktorzerlegung Die Berechnung mittels Primfaktorzerlegung lasst nativ die Berechnung fur eine beliebige Menge von Zahlen a1 ak displaystyle a 1 ldots a k zu Man verwendet alle Primfaktoren die in jeder der Zahlen vorkommen mit der jeweils kleinsten vorkommenden Potenz Gegeben seien die Primfaktorzerlegungen a1 p1e1 1p2e1 2 pme1 ma2 p1e2 1p2e2 2 pme2 m ak p1ek 1p2ek 2 pmek m displaystyle begin array ccccc a 1 amp p 1 e 1 1 amp p 2 e 1 2 amp cdots amp p m e 1 m a 2 amp p 1 e 2 1 amp p 2 e 2 2 amp cdots amp p m e 2 m vdots quad amp vdots amp vdots amp ddots amp vdots a k amp p 1 e k 1 amp p 2 e k 2 amp cdots amp p m e k m end array mit ei j 0 displaystyle e i j geq 0 dem jeweiligen Exponenten des Primfaktors pj displaystyle p j der Zahl ai displaystyle a i i 1 k j 1 m displaystyle i 1 ldots k j 1 ldots m Der ggT berechnet sich zu mit min e1 j e2 j ek j displaystyle min e 1 j e 2 j ldots e k j dem kleinsten Exponenten des Primfaktors pj displaystyle p j aller Zahlen ggT a1 a2 ak j 1mpjmin e1 j e2 j ek j displaystyle operatorname ggT a 1 a 2 ldots a k prod j 1 m p j min e 1 j e 2 j ldots e k j Beispiel Gesucht ist der kleinste gemeinsame Teiler von 1574 1760 displaystyle 1574 1760 und 1925 displaystyle 1925 Die Primfaktorenzerlegung lautet wobei die jeweils kleinsten Exponenten in Rot die anderen irrelevanten in Grau gesetzt sind 1584 24 32 50 70 111 displaystyle 1584 2 color Gray 4 cdot 3 color Gray 2 cdot 5 color Red 0 cdot 7 color Red 0 cdot 11 color Red 1 1760 25 30 51 70 111 displaystyle 1760 2 color Gray 5 cdot 3 color Red 0 cdot 5 color Gray 1 cdot 7 color Red 0 cdot 11 color Red 1 1925 20 30 52 71 111 displaystyle 1925 2 color Red 0 cdot 3 color Red 0 cdot 5 color Gray 2 cdot 7 color Gray 1 cdot 11 color Red 1 die kleinsten Exponenten sind 0 0 0 0 1 displaystyle color Red 0 color Red 0 color Red 0 color Red 0 color Red 1 Daher folgt ggT 1584 1760 1925 20 30 50 70 111 1 1 1 1 11 11 displaystyle operatorname ggT 1584 1760 1925 2 color Red 0 cdot 3 color Red 0 cdot 5 color Red 0 cdot 7 color Red 0 cdot 11 color Red 1 1 cdot 1 cdot 1 cdot 1 cdot 11 11 Bemerkung Bei Anwendung des jeweils grossten Exponenten erhalt man analog das kleinste gemeinsame Vielfache 1584 24 32 50 70 111 displaystyle 1584 2 color Gray 4 cdot 3 color Red 2 cdot 5 color Gray 0 cdot 7 color Gray 0 cdot 11 color Red 1 1760 25 30 51 70 111 displaystyle 1760 2 color Red 5 cdot 3 color Gray 0 cdot 5 color Gray 1 cdot 7 color Gray 0 cdot 11 color Red 1 1925 20 30 52 71 111 displaystyle 1925 2 color Gray 0 cdot 3 color Gray 0 cdot 5 color Red 2 cdot 7 color Red 1 cdot 11 color Red 1 die grossten Exponenten sind 5 2 2 1 1 displaystyle color Red 5 color Red 2 color Red 2 color Red 1 color Red 1 Daher folgt kgV 1584 1760 1925 25 32 52 71 111 32 9 25 7 11 554400 displaystyle operatorname kgV 1584 1760 1925 2 color Red 5 cdot 3 color Red 2 cdot 5 color Red 2 cdot 7 color Red 1 cdot 11 color Red 1 32 cdot 9 cdot 25 cdot 7 cdot 11 554 400 Das Produkt aus ggT displaystyle operatorname ggT und kgV displaystyle operatorname kgV ist 6098400 displaystyle 6 098 400 das der drei Zahlen ist 5366592000 displaystyle 5 366 592 000 womit man sieht dass die Multiplikationsregel fur ggT displaystyle operatorname ggT und kgV displaystyle operatorname kgV fur mehr als zwei Zahlen nicht gilt Berechnung mittels Verkettung Wie wir schon festgestellt haben ist die Berechnung uber die Primfaktorenzerlegung nicht die effizienteste Methode Die Berechnung des ggT displaystyle operatorname ggT erfolgt durch Verkettung Die Reihenfolge sowohl kommutativ wie assoziativ ist dabei irrelevant ggT a b c ggT ggT a b c ggT a ggT b c displaystyle operatorname ggT a b c operatorname ggT operatorname ggT a b c operatorname ggT a operatorname ggT b c ggT b a c ggT b ggT c a displaystyle qquad qquad quad operatorname ggT b a c operatorname ggT b operatorname ggT c a ldots Fur die Berechnung von ggT 1584 1760 1925 displaystyle operatorname ggT 1584 1760 1925 berechnet man z B zuerst ggT 1584 1760 176 displaystyle operatorname ggT 1584 1760 176 qquad und im zweiten Schritt ggT 176 1925 11 displaystyle operatorname ggT 176 1925 11 Der Hintergrund warum das funktioniert ist die Eigenschaft des Minimum Operators min A B min min A min B displaystyle min mathcal A cup mathcal B min min mathcal A min mathcal B der sich durch das Anwenden auf die Exponenten auf die ggT displaystyle operatorname ggT durchschlagt ggT A B ggT ggT A ggT B displaystyle operatorname ggT mathcal A cup mathcal B operatorname ggT operatorname ggT mathcal A operatorname ggT mathcal B A displaystyle mathcal A und B displaystyle mathcal B bezeichnen hier jeweils nichtleere Mengen an ganzen Zahlen d h man kann eine Menge M displaystyle mathcal M in sinnvollerweise aber nicht notwendigerweise echte nichtleere Teilemengen A M displaystyle emptyset subset mathcal A subseteq mathcal M und B M displaystyle emptyset subset mathcal B subseteq mathcal M mit A B M displaystyle mathcal A cup mathcal B mathcal M zerlegen und dann die Operation rekursiv anwenden Dies rechtfertigt die Schreibweise ggT a1 a2 an displaystyle operatorname ggT a 1 a 2 ldots a n Bemerkung Das Gleiche gilt fur das kleinste gemeinsame Vielfache nur dass hier das Minimum jeweils durch das Maximum der Exponenten ersetzt wird Berechnen fur Polynome Die Bestimmung des ggT displaystyle operatorname ggT fur Polynome lauft auf geschicktes Raten und Polynomdivisionen bzw auf die Bestimmung der Nullstellen der Polynome hinaus Letzteres erfolgt folgendermassen ggT i 0kaixi i 0mbixi ggT ak i 0k x xa i bm i 0m x xb i ggT ak bm xi M x xi displaystyle operatorname ggT left sum i 0 k a i x i sum i 0 m b i x i right operatorname ggT left a k prod i 0 k x x a i b m prod i 0 m x x b i right operatorname ggT a k b m prod x i in mathcal M x x i wobei M displaystyle mathcal M die Menge aller paarweise identischen Nullstellen der beiden Polynome umfasst Beispiel ggT 2x5 28x4 138x3 296x2 280x 96 6x5 72x4 312x3 612x2 546x 180 displaystyle operatorname ggT 2x 5 28x 4 138x 3 296x 2 280x 96 6x 5 72x 4 312x 3 612x 2 546x 180 ggT 2 x 1 x 1 x 2 x 4 x 6 6 x 1 x 1 x 2 x 3 x 5 displaystyle operatorname ggT 2 x 1 x 1 x 2 x 4 x 6 6 x 1 x 1 x 2 x 3 x 5 Die gemeinsamen Nullstellen sind die doppelte Nullstelle 1 displaystyle 1 und die einfache Nullstelle 2 displaystyle 2 weiterhin ist das ggT 2 6 2 displaystyle operatorname ggT 2 6 2 ggT 2x4 20x3 64x2 76x 30 2x4 16x3 42x2 44x 16 2 x 1 x 1 x 2 2x3 8x2 10x 4 displaystyle operatorname ggT 2x 4 20x 3 64x 2 76x 30 2x 4 16x 3 42x 2 44x 16 2 x 1 x 1 x 2 2x 3 8x 2 10x 4 Der rationale Bruch 2x5 28x4 138x3 296x2 280x 966x5 72x4 312x3 612x2 546x 180 displaystyle frac 2x 5 28x 4 138x 3 296x 2 280x 96 6x 5 72x 4 312x 3 612x 2 546x 180 lasst sich fur x 1 2 displaystyle x neq 1 2 kurzen zu x 6 x 4 3 x 5 x 3 displaystyle frac x 6 x 4 3 x 5 x 3 Lemma von Bezout Hauptartikel Lemma von Bezout Nach dem Lemma von Bezout lasst sich der grosste gemeinsame Teiler zweier ganzer Zahlen m displaystyle m und n displaystyle n als Linearkombination von m displaystyle m und n displaystyle n mit ganzzahligen Koeffizienten darstellen ggT m n s m t n displaystyle operatorname ggT m n s cdot m t cdot n mit s t Z displaystyle s t in mathbb Z Beispielsweise besitzt der grosste gemeinsame Teiler von 12 displaystyle 12 und 18 displaystyle 18 die folgende Darstellung ggT 12 18 6 1 12 1 18 displaystyle operatorname ggT 12 18 6 1 cdot 12 1 cdot 18 Die Koeffizienten s displaystyle s und t displaystyle t konnen mit dem erweiterten euklidischen Algorithmus berechnet werden SonderfalleFur gerades e displaystyle e ungerades d displaystyle d sowie ganzes i j k displaystyle i j k gilt ggT e 1 e 1 1ggT 2e e2 1 1ggT 2d d2 1 2ggT 2k k 1 2k 1 1ggT 4k 4k2 1 1ggT i j 1 i j ggT 1 2j 1 2i ggT a b 2ggT a2 b2 falls a und b geradeggT a b ggT a2 b falls a gerade und b ungeradeggT a b ggT a b2 b falls a und b ungerade displaystyle begin array lll operatorname ggT e 1 e 1 amp 1 operatorname ggT 2e e 2 1 amp 1 operatorname ggT 2d d 2 1 amp 2 operatorname ggT 2k k 1 2k 1 amp 1 operatorname ggT 4k 4k 2 1 amp 1 operatorname ggT i j 1 i j amp operatorname ggT 1 2j 1 2i operatorname ggT a b amp 2 operatorname ggT big tfrac a 2 tfrac b 2 big amp text falls a text und b text gerade operatorname ggT a b amp operatorname ggT big tfrac a 2 b big amp text falls a text gerade und b text ungerade operatorname ggT a b amp operatorname ggT big tfrac a b 2 b big amp text falls a text und b text ungerade end array Setzt man eine Primzahl aus zwei echten Summanden zusammen gilt fur diese stets Teilerfremdheit Aus p a b 0 lt b a lt p a N b N p P displaystyle p a b 0 lt b leq a lt p a in mathbb N b in mathbb N p in mathbb P folgt ggT a b 1 displaystyle operatorname ggT a b 1 AnwendungenKurzen von Bruchen Beim Kurzen wird ein gemeinsamer Faktor von Zahler und Nenner eines Bruches entfernt wobei sich der Wert des Bruches nicht andert z B 1218 6 29 2 69 displaystyle tfrac 12 18 tfrac 6 cdot 2 9 cdot 2 tfrac 6 9 Kurzt man mit dem grossten gemeinsamen Teiler von Zahler und Nenner entsteht ein Bruch der nicht weiter kurzbar ist Zum Beispiel ist ggT 12 18 6 displaystyle operatorname ggT 12 18 color Red 6 also 1218 2 63 6 23 displaystyle frac 12 18 frac 2 cdot color Red 6 3 cdot color Red 6 frac 2 3 Ein Bruch mit Zahler a displaystyle a und Nenner b displaystyle b bei dem ggT a b 1 displaystyle operatorname ggT a b 1 ist ist nicht weiter kurzbar Er wird voll gekurzt in der Mathematik vollstandig oder maximal gekurzter Bruch genannt In der englischsprachigen Literatur wird er Simplified fraction oder Reduced fraction genannt Zusammenhang zwischen grosstem gemeinsamen Teiler ggT und kleinstem gemeinsamen Vielfachen kgV Satz ggT a b kgV a b a b displaystyle operatorname ggT a b cdot operatorname kgV a b a cdot b Beweis Nachweis fur positive ganze Zahlen m displaystyle m und n displaystyle n alle anderen Falle lassen sich analog behandeln Sei k kgV m n displaystyle k operatorname kgV m n dann ist k displaystyle k auch Teiler des Produkts m n displaystyle m cdot n Die Zahl g displaystyle g enthalte dagegen alle Primfaktoren des Produkts m n displaystyle m cdot n die k displaystyle k nicht enthalt Betrachtet man wie der ggT m n displaystyle operatorname ggT m n aus der Primfaktordarstellung des Produkts aus m displaystyle m und n displaystyle n berechnet wird dann folgt g ggT m n displaystyle g operatorname ggT m n Daraus ergibt sich die obige Gleichung Weitere algebraische Strukturen mit ggTDer Begriff des ggT displaystyle operatorname ggT baut auf dem Begriff der Teilbarkeit auf wie er in Ringen definiert ist Man beschrankt sich bei der Diskussion des ggT displaystyle operatorname ggT auf nullteilerfreie Ringe im kommutativen Fall sind das die Integritatsringe Ein Integritatsring in dem je zwei Elemente einen ggT displaystyle operatorname ggT besitzen heisst oder ggT Bereich In einem ggT displaystyle operatorname ggT Ring haben je zwei Elemente auch ein kgV displaystyle operatorname kgV Im Allgemeinen besitzen solche Ringe keine Halbordnung die antisymmetrisch ist wie die ganzen oder die naturlichen Zahlen eine haben Haufig ist die Teilbarkeitsrelation die eine Quasiordnung ist die einzige Ordnungsrelation Deshalb lasst sich der ggT displaystyle operatorname ggT gegebenenfalls nicht mehr eindeutig als nicht negativ normieren sondern nur bis auf Assoziiertheit bestimmen Zwei Elemente a displaystyle a und b displaystyle b sind assoziiert in Zeichen a b displaystyle a sim b wenn es eine Einheit ϵ displaystyle epsilon mit a b ϵ displaystyle a b cdot epsilon gibt Wir erweitern den Begriff des ggT displaystyle operatorname ggT auf die Menge aller grossten gemeinsamen Teiler der Elemente einer Teilmenge M displaystyle M eines Ringes R displaystyle R formal d ggT M y R x M y x y d displaystyle d in operatorname ggT M quad Longleftrightarrow quad forall y in R forall x in M y mid x Leftrightarrow y mid d In Worten Die Teiler von d displaystyle d sind genau die Elemente aus R displaystyle R die alle Elemente aus M displaystyle M teilen Die ggT displaystyle operatorname ggT sind untereinander assoziiert Polynomringe Man kann den ggT displaystyle operatorname ggT z B auch fur Polynome bilden Statt der Primfaktorzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren f X Y X2 2XY Y2 X Y 2g X Y X2 Y2 X Y X Y displaystyle begin aligned f X Y amp X 2 2XY Y 2 X Y 2 g X Y amp X 2 Y 2 X Y X Y end aligned