Größter gemeinsamer Teiler

Grundidee und Definition

Der größte gemeinsame Teiler, kurz ggT, ist die größte natürliche beziehungsweise ganze positive Zahl m, durch die sich zwei oder mehr gegebene ganze Zahlen ohne Rest teilen lassen. Ist der ggT zweier Zahlen 1, heißen sie teilerfremd. Beispiel: ggT(10, 15) = 5, weil 5 sowohl 10 als auch 15 teilt. Der Bruch 10/15 kann deshalb zu 2/3 gekürzt werden; 2 und 3 sind dann teilerfremd.

Für zwei ganze Zahlen a und b, von denen mindestens eine ungleich 0 ist, ist ggT(a, b) die größte ganze Zahl m, für die es ganze Zahlen α und β gibt mit a = m · α und b = m · β. In deutschsprachigen Texten schreibt man ggT(a, b), in englischsprachigen Texten gcd(a, b) für greatest common divisor.

Sonderfälle mit 0 werden meist so festgelegt: ggT(0, a) = |a|. Daraus folgt auch ggT(0, 0) = 0. Einige Autoren lassen ggT(0, 0) jedoch undefiniert. Die Konvention ggT(0, 0) = 0 wird häufig verwendet, weil sie etwa die Bézout-Identität und den Abschluss des euklidischen Algorithmus vereinfacht.

Wichtig ist auch die allgemeinere Sicht: Die gemeinsamen Teiler von a und b sind genau die Teiler ihres ggT. Diese Bedeutung von „größter“ ist entscheidend, wenn der Begriff später auf andere mathematische Strukturen wie Polynome oder Ringe übertragen wird.

Beispiele und Rechenregeln

Bei ggT(12, 18) haben 12 und 18 die gemeinsamen Teiler 1, 2, 3 und 6. Der größte davon ist 6, also ggT(12, 18) = 6. Bei drei Zahlen funktioniert die Idee genauso: 12, 18 und 30 haben ebenfalls die gemeinsamen Teiler 1, 2, 3 und 6, daher gilt ggT(12, 18, 30) = 6.

Wichtige Rechenregeln für ganze Zahlen a, b, c und k sind: ggT(a, b) = ggT(b, a) (Kommutativgesetz), ggT(a, b, c) = ggT(a, ggT(b, c)) = ggT(ggT(a, b), c) (Assoziativgesetz) und ggT(k·a, k·b) = |k|·ggT(a, b). Außerdem gilt ggT(±a, ±b) = ggT(a, b), ggT(a, 0) = |a|, ggT(a, 1) = 1 und ggT(a, a) = |a|.

Für a,b ≠ 0 gilt ggT(a, b) = ggT(a, b mod a) = ggT(a mod b, b). Diese Regel ist die Grundlage des euklidischen Algorithmus. Ebenfalls wichtig ist: Wenn k ein gemeinsamer Teiler von a und b ist und k ≠ 0, dann teilt k den ggT(a, b), und es gilt ggT(a/k, b/k) = ggT(a, b)/|k|. Sind a und b teilerfremd, dann gilt für festes c: ggT(ab, c) = ggT(a, c) · ggT(b, c).

Berechnung des ggT

Eine Methode ist die Primfaktorzerlegung. Man zerlegt beide Zahlen in Primfaktoren und nimmt alle Primfaktoren, die in beiden Zahlen vorkommen, jeweils mit der kleinsten vorkommenden Potenz. Sind a = p1^α1 · p2^α2 · ... · pm^αm und b = p1^β1 · p2^β2 · ... · pm^βm, dann gilt ggT(a, b) = Produkt über pj^min(αj, βj). Beispiel: Aus den Primfaktorzerlegungen von 2970 und 12 936 ergeben sich die kleinsten Exponenten zu 2^1 · 3^1 · 5^0 · 7^0 · 11^1 = 66. Also ist ggT(2970, 12 936) = 66.

Für große Zahlen ist die Primfaktorzerlegung sehr aufwändig. Effizienter ist der euklidische Algorithmus. Beim modernen Verfahren teilt man wiederholt mit Rest: Im nächsten Schritt wird der Divisor zum neuen Dividenden und der Rest zum neuen Divisor. Der letzte Divisor, bei dem der Rest 0 entsteht, ist der ggT. Beispiel: 143 / 65 hat Rest 13, danach 65 / 13 Rest 0. Also ist ggT(143, 65) = 13.

Der ursprüngliche euklidische Algorithmus arbeitet mit wiederholtem Subtrahieren der kleineren Zahl von der größeren. Der steinsche Algorithmus ist eine Abwandlung davon, die Divisionen vermeidet. Auf aktuellen CPUs läuft er laut Artikel etwa dreimal langsamer als der euklidische Algorithmus mit Modulo-Operation, weil er viele schlecht vorhersagbare Sprünge verwendet. Eine einfache, aber meist langsame Methode ist das Probieren: Man zählt von der kleinsten Zahl abwärts und prüft, welche Zahl alle gegebenen Zahlen teilt.

Für mehrere Zahlen kann man entweder die Primfaktorzerlegung mit den jeweils kleinsten Exponenten aller Zahlen verwenden oder den ggT verketten: ggT(a, b, c) = ggT(ggT(a, b), c) = ggT(a, ggT(b, c)). Beim Beispiel ggT(1584, 1760, 1925) berechnet man zuerst ggT(1584, 1760) = 176 und dann ggT(176, 1925) = 11.

Brüche, kgV und Bézout

Die wichtigste Anwendung in der Schulmathematik ist das Kürzen von Brüchen. Beim Kürzen wird ein gemeinsamer Faktor von Zähler und Nenner entfernt, ohne den Wert des Bruchs zu ändern. Kürzt man mit dem größten gemeinsamen Teiler von Zähler und Nenner, entsteht ein vollständig gekürzter Bruch. Beispiel: ggT(12, 18) = 6, daher gilt 12/18 = (2·6)/(3·6) = 2/3. Ein Bruch mit Zähler a und Nenner b ist genau dann nicht weiter kürzbar, wenn ggT(a, b) = 1.

Das Pendant des ggT ist das kleinste gemeinsame Vielfache, kurz kgV. Für zwei Zahlen gilt die wichtige Beziehung ggT(a, b) · kgV(a, b) = |ab| beziehungsweise für positive Zahlen ggT(a, b) · kgV(a, b) = a · b. Für mehr als zwei Zahlen gilt diese einfache Multiplikationsregel im Allgemeinen nicht; im Artikel zeigt das Beispiel ggT(1584, 1760, 1925) = 11 und kgV(1584, 1760, 1925) = 554 400, deren Produkt 6 098 400 nicht dem Produkt der drei Zahlen 5 366 592 000 entspricht.

Nach dem Lemma von Bézout lässt sich der größte gemeinsame Teiler zweier ganzer Zahlen m und n als Linearkombination dieser Zahlen darstellen: ggT(m, n) = s·m + t·n mit s,t ∈ Z. Beispiel: ggT(12, 18) = 6 = (-1)·12 + 1·18. Die Koeffizienten s und t kann man mit dem erweiterten euklidischen Algorithmus berechnen.

Polynome und andere Strukturen

Das Konzept des ggT lässt sich auf Polynome und andere algebraische Strukturen erweitern. Bei Polynomen misst man die „Größe“ oft über den Polynomgrad. Im Ring Z[x] gilt zum Beispiel ggT(x^2 - 1, x + 1) = x + 1, weil x^2 - 1 die Faktoren x + 1 und x - 1 hat und x + 1 ein gemeinsamer Teiler ist.

Für Polynome kann man den ggT durch Zerlegung in irreduzible Faktoren, Polynomdivision oder über gemeinsame Nullstellen bestimmen. Im Artikel wird etwa beschrieben, dass gemeinsame Nullstellen gemeinsame Faktoren liefern. Bei einem rationalen Bruch aus Polynomen kann man gemeinsame Polynomfaktoren kürzen, allerdings nur für Werte, bei denen die gekürzten Faktoren nicht 0 werden.

Allgemeiner baut der ggT auf dem Begriff der Teilbarkeit in Ringen auf. Ein Integritätsring, in dem je zwei Elemente einen ggT besitzen, heißt ggT-Ring oder ggT-Bereich. In solchen Strukturen ist der ggT oft nicht eindeutig als nichtnegative Zahl bestimmbar, sondern nur bis auf Assoziiertheit. Zwei Elemente a und b heißen assoziiert, geschrieben a ~ b, wenn es eine Einheit ε mit a = b·ε gibt.

Im gaußschen Zahlenring Z + iZ ist 1 + i ein größter gemeinsamer Teiler von 2 und 1 + 3i, denn 2 = -i(1 + i)^2 und 1 + 3i = (1 + i)(2 + i). Da die Einheiten dort ±1 und ±i sind, sind auch alle zu 1 + i assoziierten Zahlen größte gemeinsame Teiler. Es gibt außerdem Integritätsringe, in denen zwei Elemente keinen ggT besitzen; der Artikel nennt R = Z[√-3] als Beispiel.

Zahlentheorie und Sonderfälle

In der elementaren Zahlentheorie gehört der größte gemeinsame Teiler t zweier ganzer Zahlen m,n ∈ Z \ {0} zu den wichtigsten Grundkonzepten. Häufig schreibt man dort t = (m, n) und meint damit den positiven ggT, also t ∈ N. In der analytischen Zahlentheorie kann die ggT-Funktion Z \ {0} → N; m ↦ (m, n) für festes n ∈ N \ {0} analytisch zu einer ganzen Funktion fortgesetzt werden; der Artikel verweist dazu auf die Ramanujansumme.

Der Artikel nennt außerdem mehrere Sonderfälle. Für gerades e gilt ggT(e - 1, e + 1) = 1 und ggT(2e, e^2 - 1) = 1. Für ungerades d gilt ggT(2d, d^2 - 1) = 2. Weitere Regeln sind zum Beispiel ggT(2k(k + 1), 2k + 1) = 1 und ggT(4k, 4k^2 - 1) = 1.

Auch Paritätsregeln spielen eine Rolle: Sind a und b gerade, dann gilt ggT(a, b) = 2·ggT(a/2, b/2). Ist a gerade und b ungerade, gilt ggT(a, b) = ggT(a/2, b). Sind a und b ungerade, gilt ggT(a, b) = ggT((a - b)/2, b). Diese Regeln stehen in Beziehung zu Verfahren wie dem steinschen Algorithmus.