Hauptmenü öffnen

Größter gemeinsamer Teiler

mathematische Funktion

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

Er 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, ihrerseits 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.[1]

Inhaltsverzeichnis

BeispielBearbeiten

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

BerechnungBearbeiten

Berechnung über die PrimfaktorzerlegungBearbeiten

GgT und kgV kann man über die Primfaktorzerlegung der beiden gegebenen Zahlen bestimmen. Beispiel:

  •  
  •  

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

  •  

Euklidischer und steinscher AlgorithmusBearbeiten

Die Berechnung der Primfaktorzerlegung großer Zahlen und damit auch die Bestimmung des größten gemeinsamen Teilers nach obiger Methode ist sehr aufwändig. Mit dem euklidischen Algorithmus existiert jedoch ein effizientes Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen. Dieses Verfahren wurde durch den steinschen Algorithmus noch weiter variiert. Ob dies eine Verbesserung ist, hängt von der jeweiligen Bewertungsfunktion und „Maschinerie“ ab, die den jeweiligen Algorithmus ausführt.

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 abgezogen und dieser Schritt mit dem Ergebnis und der kleineren Länge so lange wiederholt, bis die abgezogene Zahl mit dem Ergebnis identisch ist. Beispiel:

 

Der größte gemeinsame Teiler ist somit 13. Wenn man weiß, dass 13 prim ist, könnte man im Beispiel schon im zweiten Schritt den Teiler ablesen, da eine Primzahl als Ergebnis nicht weiter geteilt werden kann.

Beim modernen euklidischen Algorithmus wird in aufeinanderfolgenden Schritten jeweils eine Division mit Rest durchgeführt, wobei der Rest im nächsten Schritt zum neuen Divisor wird. Der Divisor, bei dem sich Rest 0 ergibt, ist der größte gemeinsame Teiler der Ausgangszahlen. Beispiel:

 

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

In 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);
}

Der ggT von mehreren ZahlenBearbeiten

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 ggT assoziativ:

 

Dies rechtfertigt die Schreibweise  .

RechenregelnBearbeiten

Seien  ,  ,   und   ganze Zahlen. Dann gilt:

 

Dabei bezeichnet   den 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.

Ist   ein gemeinsamer Teiler von   und  , dann gilt:

    teilt       und
 

Ist     (  und   sind kongruent modulo  ), dann gilt:

 

Hält man eines der beiden Argumente fest, dann ist ggT eine multiplikative Funktion, denn für teilerfremde Zahlen   und   gilt

 

Lemma von BézoutBearbeiten

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älleBearbeiten

Für gerades  , ungerades   sowie ganzes   gilt:

 ;
 ;
 ;
 .

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

 .

AnwendungenBearbeiten

BruchrechnungBearbeiten

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, der nicht weiter kürzbar ist, wird gekürzter Bruch oder auch vollständig und maximal gekürzter Bruch genannt.

Zusammenhang zwischen ggT und dem kleinsten gemeinsamen VielfachenBearbeiten

siehe Kleinstes gemeinsames Vielfaches#Zusammenhang zwischen kgV und dem größten gemeinsamen Teiler

Weitere algebraische Strukturen mit ggTBearbeiten

Der Begriff des ggT baut auf dem Begriff der Teilbarkeit auf, wie er in Ringen definiert ist. Man beschränkt sich bei der Diskussion des ggT auf nullteilerfreie Ringe, im kommutativen Fall sind das die Integritätsringe.

Ein Integritätsring, in dem je zwei Elemente einen ggT besitzen, heißt ggT-Ring oder ggT-Bereich. (In einem ggT-Ring haben je zwei Elemente auch ein 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 ggT ggfls. 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 ggT 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 ggT sind untereinander assoziiert.

PolynomringeBearbeiten

Man kann den ggT 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 ZahlenringBearbeiten

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ätsringeBearbeiten

Im Integritätsring   haben die Elemente

 

keinen ggT: 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 ggT von   und  .

Die genannten Elemente   und   haben aber ihrerseits einen ggT, nämlich  . Dagegen haben sie kein kgV, denn wenn   ein kgV 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 kgV und die beiden Elemente haben gar kein kgV.

Ist   ein Integritätsring und haben die Elemente   und   ein kgV, dann haben sie auch einen ggT, 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 ZahlentheorieBearbeiten

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 ggT, 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.

EinzelnachweiseBearbeiten

  1. Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8, S. 15.

LiteraturBearbeiten

WeblinksBearbeiten