Größter gemeinsamer Teiler

Der größte gemeinsame Teiler (ggT) ist ein mathematischer Begriff. Sein Pendant ist das kleinste gemeinsame Vielfache (kgV). Beide spielen unter anderem in der Arithmetik und der Zahlentheorie eine Rolle.

Der  ist die größte natürliche Zahl, durch die sich zwei ganze Zahlen ohne Rest teilen lassen. Der  zweier ganzer Zahlen  und  ist eine ganze Zahl  mit der Eigenschaft, dass sie Teiler sowohl von  als auch von  ist und dass jede ganze Zahl, die ebenfalls die Zahlen  und  teilt, auch Teiler von  ist. Beim Ring  der ganzen Zahlen (der eine Totalordnung > besitzt) normiert man den  auf die größte ganze solche Zahl .

Der Begriff „groß“ in  korreliert hochgradig mit der üblichen Ordnungsrelation > der ganzen Zahlen. Es gibt allerdings eine wichtige Ausnahme: Da die  Vielfaches einer jeden ganzen Zahl  ist, ist  in Teilbarkeitsfragen an „Größe“ nicht zu überbieten. Diese Auffassung ist in Einklang mit der Verbandsvorstellung (und der Idealtheorie) und vereinfacht einige der unten aufgeführten Rechenregeln.

Die englische Bezeichnung gcd (greatest common divisor) für  ist in mathematischen Texten ebenfalls verbreitet.

Oft wird auch  als Kurzschreibweise für  verwendet.

Beispiel 
 12 ist durch die folgenden Zahlen ohne Rest teilbar: 1, 2, 3, 4, 6, 12.
 18 hat diese Teiler: 1, 2, 3, 6, 9, 18.
 Die gemeinsamen Teiler von 12 und 18 sind also 1, 2, 3, 6 und der größte von diesen ist 6 – in Zeichen:

Berechnung

Berechnung über die Primfaktorzerlegung 
Man kann den  über die Primfaktorzerlegung der beiden gegebenen Zahlen bestimmen. Beispiel:

 
 

Für den  nimmt man die Primfaktoren, die in beiden Zerlegungen vorkommen, und als zugehörigen Exponenten den jeweils kleineren der Ausgangsexponenten:

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. Mit dem euklidischen Algorithmus existiert jedoch auch ein effizientes Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen.

Der klassische euklidische Algorithmus 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 3780 und 3528:

Somit ist 252 der größte gemeinsame Teiler von 3780 und 3528.

In der Programmiersprache C wird der Algorithmus wie folgt formuliert:

int GreatestCommonDivisor(int a, int b)
{
    int h;
    if (a == 0) return abs(b);
    if (b == 0) return abs(a);

    do {
        h = a % b;
        a = b;
        b = h;
    } while (b != 0);

    return abs(a);
}Eine Variante mit Rekursion ist wie folgt formuliert:int GreatestCommonDivisor(int a, int b) {
  if (a == 0)
    return b;
  if (b == 0)
    return a;
  if (a < b)
    return GreatestCommonDivisor(b, a);
  return GreatestCommonDivisor(b, a % b);
}

Steinscher Algorithmus 
Der steinsche Algorithmus ist eine Variation des euklidischen Algorithmus. Ob er eine Verbesserung darstellt, hängt von der jeweiligen Bewertungsfunktion und „Maschinerie“ ab, die den jeweiligen Algorithmus ausführt.

Der ggT von mehreren Zahlen 

Man verwendet alle Primfaktoren, die in jeder der Zahlen vorkommen, mit der jeweils kleinsten vorkommenden Potenz, zum Beispiel:

also:

Man könnte auch zunächst  berechnen und danach  denn als eine zweistellige Verknüpfung auf den natürlichen Zahlen ist der  assoziativ:

Dies rechtfertigt die Schreibweise .

Rechenregeln 
Für ganze Zahlen  gilt – mit  als dem Betrag von :

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:

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:
;
;
;
;
;
, falls  und  gerade.
, falls  gerade und  ungerade.
, falls  und  ungerade.

Setzt man eine Primzahl aus zwei echten Summanden zusammen, gilt für diese stets Teilerfremdheit:
 Aus  folgt .

Anwendungen

Bruchrechnung 
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 oder auch vollständig oder maximal gekürzter Bruch genannt.

Zusammenhang zwischen ggT und dem kleinsten gemeinsamen Vielfachen 

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 ggT-Ring oder ggT-Bereich. (In einem -Ring haben je zwei Elemente auch ein \operatorname{kgV}.)

In 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:

Dann ist

Der Polynomring  in einer Variablen  ist euklidisch. Dort gibt es zur Berechnung des  eine Division mit Rest.

Gaußscher Zahlenring 
Im gaußschen Zahlenring  ist der größte gemeinsame Teiler von  und  gerade , denn  und . Genau genommen ist  nur ein größter gemeinsamer Teiler, da alle zu dieser Zahl assoziierten Zahlen ebenfalls größte gemeinsame Teiler sind. (Die Einheiten sind .)

Integritätsringe 
Im Integritätsring  haben die Elemente

keinen : Die Elemente  und  sind zwei maximale gemeinsame Teiler, denn beide haben den gleichen Betrag, aber diese zwei Elemente sind nicht zueinander assoziiert. Also gibt es keinen  von  und .

Die genannten Elemente  und  haben aber ihrerseits einen , nämlich . Dagegen haben sie kein , denn wenn  ein  wäre, dann folgt aus der „ggT-kgV-Gleichung“, dass  assoziiert zu  sein muss. Das gemeinsame Vielfache  ist jedoch kein Vielfaches von , also ist  kein  und die beiden Elemente haben gar kein .

Ist  ein Integritätsring und haben die Elemente  und  ein , dann haben sie auch einen , und es gilt die Gleichung:

Ein euklidischer Ring ist ein Hauptidealring, der ein faktorieller Ring ist, der schließlich ein ggT-Ring ist. Ebenso ist jeder Hauptidealring ein Bézoutring, der wiederum stets ein ggT-Ring ist.

Ein Beispiel für einen nicht-kommutativen ggT-Ring sind die Hurwitzquaternionen.

Analytische Zahlentheorie 
In der elementaren Zahlentheorie gehört der größte gemeinsame Teiler  von zwei ganzen Zahlen  zu den wichtigsten Grundkonzepten. Man schreibt dort regelmäßig  und meint damit dann den positiven , geht also von  aus.

In der analytischen Zahlentheorie kann die ggT-Funktion  in einer Variablen für festes  analytisch zu einer ganzen Funktion fortgesetzt werden. → Siehe Ramanujansumme.

Einzelnachweise

Literatur 
 Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8.
 Universität Ulm: Elementare Zahlentheorie.

Weblinks 

 Verschiedene Online-Tools zur Primfaktorzerlegung, ggT und kgV.
 Skriptum: (PDF; 1,0 MB) Analytische Fortsetzung des ggT zu einer ganzen Funktion.
 Christian Spannagel: Der Euklidische Algorithmus. Vorlesungsreihe, 2012.
 Christian Spannagel: Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache. Vorlesungsreihe, 2012.

Arithmetik
Zahlentheorie