Größter gemeinsamer Teiler
- Zahlentheoretische 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.
Der
Der Begriff „groß“ in
Die englische Bezeichnung gcd (greatest common divisor) für
Oft wird auch
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
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 Algorithmus
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!
Beim 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 21 der größte gemeinsame Teiler von 1071 und 1029.
Rechenregeln
Seien
Dabei bezeichnet
Aus der genannten Rechenregel
Ist
teilt und
Ist
Hält man eines der beiden Argumente fest, dann ist ggT eine multiplikative Funktion, denn für teilerfremde Zahlen
Lemma von Bézout
Nach dem Lemma von Bézout lässt sich der größte gemeinsame Teiler zweier ganzer Zahlen
mit
Beispielsweise besitzt der größte gemeinsame Teiler von
Die Koeffizienten
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.
Zusammenhang zwischen ggT und dem kleinsten gemeinsamen Vielfachen
→ siehe Kleinstes gemeinsames Vielfaches#Zusammenhang von kgV und ggT
Weitere algebraischen Strukturen mit ggT
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
Wir erweitern den Begriff des ggT auf die Menge aller größten gemeinsamen Teiler der Elemente einer Teilmenge
.
In Worten:
Polynomringe
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
Gaußscher Zahlenring
Im gaußschen Zahlenring
Integritätsringe
Im Integritätsring
keinen ggT: Die Elemente
Die genannten Elemente
Ist
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.
Siehe auch
- Faktorieller Ring
- Hauptidealring
- Euklidischer Ring
- Polynomring
- Betrachtet man anstatt einzelner Größen, die von ihnen erzeugten Ideale im Ring, ergibt sich ein neuer Blick auf die Teilbarkeitsbeziehungen (s. „Ideale Zahlen“).
Analytische Zahlentheorie
In der elementaren Zahlentheorie gehört der größte gemeinsame Teiler
In der analytischen Zahlentheorie kann die ggT-Funktion
Einzelnachweise
- ↑ Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8, S. 15.
Literatur
- Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8.
Weblinks
- Verschiedene Online-Tools zur Primfaktorzerlegung, ggT und kgV.