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 Bruchrechnung und der Zahlentheorie eine Rolle.

Der $ \operatorname {ggT} $ zweier ganzer Zahlen $ a $ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b ist eine ganze Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m mit der Eigenschaft, dass sie Teiler sowohl von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a als auch von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b ist und dass jede ganze Zahl, die ebenfalls die Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b teilt, ihrerseits Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m ist. Beim Ring $ \mathbb {Z} $ der ganzen Zahlen (der eine Totalordnung > besitzt) normiert man den Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT} auf die größte ganze solche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): |m| .

Der Begriff „groß“ in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT} korreliert hochgradig mit der üblichen Ordnungsrelation > der ganzen Zahlen. Es gibt allerdings eine wichtige Ausnahme: Da die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 0 Vielfaches einer jeden ganzen Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m ist, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 0 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 $ \operatorname {ggT} $ ist in mathematischen Texten ebenfalls verbreitet.

Oft wird auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): (a,\, b) als Kurzschreibweise für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(a, b) verwendet.^[1]

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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(12, 18) = 6

Berechnung

Berechnung über die Primfaktorzerlegung

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

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 3528 = 2^{\color{Red}3} \cdot 3^{\color{Red}2} \cdot 7^{\color{Red}2}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 3780= 2^{\color{OliveGreen}2} \cdot 3^{\color{OliveGreen}3} \cdot 5^{\color{OliveGreen}1} \cdot 7^{\color{OliveGreen}1}

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

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(3528,3780) = 2^{\color{OliveGreen}2} \cdot 3^{\color{Red}2} \cdot 7^{\color{OliveGreen}1} = 252

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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \begin{align} 1071 &: 1029 &= \ &1 &\ \operatorname{Rest} &\ 42\\ 1029 &: 42 &= \ &24 &\ \operatorname{Rest} &\ 21\\ 42 &: 21 &= \ &2 &\ \operatorname{Rest} &\ 0 \end{align}

Somit ist 21 der größte gemeinsame Teiler von 1071 und 1029.

Rechenregeln

Seien $ a $, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m ganze Zahlen. Dann gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \begin{align} \operatorname{ggT}(a, b) &= \operatorname{ggT}(b, a) &\text{(Kommutativgesetz)}\\ \operatorname{ggT}(\pm a, \pm b) &= \operatorname{ggT}(a, b)\\ \operatorname{ggT}(a, a) &= |a|\\ \operatorname{ggT}(a, 0) &= |a|\\ \operatorname{ggT}(a, 1) &= 1\\ \operatorname{ggT}(a, b \;\bmod\; a) &= \operatorname{ggT}(a,b) &(a > 0)\\ \operatorname{ggT}(a, b + m a) &= \operatorname{ggT}(a, b)\\ \operatorname{ggT}(m a, m b) &= |m| \cdot\operatorname{ggT}(a, b) &\text{(Distributivgesetz)}\\ \operatorname{ggT}(a,b,c)&:=\operatorname{ggT}(a,\,\operatorname{ggT}(b,c)) = \operatorname{ggT}(\operatorname{ggT}(a,b),\,c) &\text{(Assoziativgesetz)}\\ \end{align}

Dabei bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): |a| den Betrag von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a .

Aus der genannten Rechenregel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(a, 0) = |a| ergibt sich speziell Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(0, 0)=0 . Dies ergibt sich auch daraus, dass jede ganze Zahl $ m $ (sogar die 0 selbst) wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m\cdot0=0 Teiler der 0 ist, während umgekehrt 0 keine von 0 verschiedene Zahl teilt.

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m \ne 0 ein gemeinsamer Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b , dann gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m teilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(a, b) und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(a: m, b: m) = \operatorname{ggT}(a, b): |m|

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a \equiv b\ \bmod\ m ($ a $ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b sind kongruent modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m ), dann gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(a, m) = \operatorname{ggT}(b, m)

Hält man eines der beiden Argumente fest, dann ist ggT eine multiplikative Funktion, denn für teilerfremde Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(a b, m) = \operatorname{ggT}(a, m) \cdot\operatorname{ggT}(b, m)

Lemma von Bézout

Nach dem Lemma von Bézout lässt sich der größte gemeinsame Teiler zweier ganzer Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): n als Linearkombination von $ m $ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): n mit ganzzahligen Koeffizienten darstellen:

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(m,n) = s \cdot m + t \cdot n mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): s,t\in\mathbb{Z}

Beispielsweise besitzt der größte gemeinsame Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 12 und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 18 die folgende Darstellung:

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(12,18) = 6 = (-1)\cdot 12 + 1\cdot 18

Die Koeffizienten $ s $ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): t können mit dem erweiterten euklidischen Algorithmus berechnet werden.

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. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \tfrac{12}{18} = \tfrac{6 \cdot 2}{9 \cdot 2} = \tfrac{6}{9} . 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(12, 18) = {\color{Blue} 6} , also

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \frac{12}{18} = \frac{2 \cdot {\color{Blue} 6}}{3 \cdot {\color{Blue} 6}} = \frac{2}{3}

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b sind assoziiert, in Zeichen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a \sim b , wenn es eine Einheit $ \epsilon \, $ mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a = b \cdot \epsilon gibt.

Wir erweitern den Begriff des ggT auf die Menge aller größten gemeinsamen Teiler der Elemente einer Teilmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): M eines Ringes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): R , formal:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): d \in \operatorname{ggT}(M)\quad:\Longleftrightarrow\quad \left(\forall x\in M: d\mid x \right) \land \left(\forall y\in R: \forall x\in M: y\mid x\Rightarrow y\mid d \right) .

In Worten: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): d teilt alle Elemente aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): M und wird selbst von allen Elementen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): R geteilt, die ebenfalls alle Elemente aus $ M $ teilen. Die ggT sind untereinander assoziiert.

Polynomringe

Man kann den ggT z. B. auch für Polynome bilden. Statt der Primfaktorzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \begin{align} f(X) &= X^2 + 2XY + Y^2 = (X + Y)^2\\ g(X) &= X^2 - Y^2 = (X + Y) (X - Y) \end{align}

Dann ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT}(f, g) \sim X + Y

Der Polynomring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \Q[X] in einer Variablen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): X ist euklidisch. Dort gibt es zur Berechnung des Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{ggT} eine Division mit Rest.

Gaußscher Zahlenring

Im gaußschen Zahlenring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \Z+\mathrm{i}\Z ist der größte gemeinsame Teiler von $ 2 $ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 1 + 3\mathrm{i} gerade Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 1 + \mathrm{i} , denn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 2 = -\mathrm{i} (1 + \mathrm{i})^2 und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 1 + 3\mathrm{i} = (1 + \mathrm{i}) (2 + \mathrm{i}) . Genau genommen ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 1 + \mathrm{i} nur ein größter gemeinsamer Teiler, da alle zu dieser Zahl assoziierten Zahlen ebenfalls größte gemeinsame Teiler sind. (Die Einheiten sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \pm 1, \pm \mathrm{i} .)

Integritätsringe

Im Integritätsring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): R = \mathbb{Z}[\sqrt{-3}] haben die Elemente

$ a:=4=2\cdot 2=(1+{\sqrt {-3}})(1-{\sqrt {-3}}),\quad b:=(1+{\sqrt {-3}})\cdot 2 $

keinen ggT: Die Elemente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 1 + \sqrt{-3} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 2 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b .

Die genannten Elemente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 1+\sqrt{-3} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 2 haben aber ihrerseits einen ggT, nämlich $ 1 $. Dagegen haben sie kein kgV, denn wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): v ein kgV wäre, dann folgt aus der „ggT-kgV-Gleichung“, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): v assoziiert zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): k:=(1 + \sqrt{-3})\cdot2 sein muss. Das gemeinsame Vielfache Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 4 ist jedoch kein Vielfaches von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): k , also ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): k kein kgV und die beiden Elemente haben gar kein kgV.

Ist $ R $ ein Integritätsring und haben die Elemente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): b ein kgV, dann haben sie auch einen ggT, und es gilt die Gleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): a \cdot b \sim \operatorname{ggT}(a, b) \cdot \operatorname{kgV}(a, b)

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): g von zwei ganzen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m,n\in\Z\setminus \lbrace 0 \rbrace zu den wichtigsten Grundkonzepten. Man schreibt dort regelmäßig Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): g=(m,n) und meint damit dann den positiven ggT, geht also von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): g\in\N aus.

In der analytischen Zahlentheorie kann die ggT-Funktion $ \mathbb {Z} \setminus \lbrace 0\rbrace \rightarrow \mathbb {N} ;\;m\mapsto (m,n) $ in einer Variablen für festes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): n\in\N\setminus \lbrace 0 \rbrace 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.

Weblinks

• Verschiedene Online-Tools zur Primfaktorzerlegung, ggT und kgV.