Größter gemeinsamer Teiler

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 b ist eine ganze Zahl m mit der Eigenschaft, dass sie Teiler sowohl von a als auch von b ist und dass jede ganze Zahl, die ebenfalls die Zahlen a und b teilt, ihrerseits Teiler von m ist. Beim Ring \Z der ganzen Zahlen (der eine Totalordnung > besitzt) normiert man den \operatorname{ggT} auf die größte ganze solche Zahl | m | .

Der Begriff „groß“ in \operatorname{ggT} korreliert hochgradig mit der üblichen Ordnungsrelation > der ganzen Zahlen. Es gibt allerdings eine wichtige Ausnahme: Da die 0 Vielfaches einer jeden ganzen Zahl m ist, ist 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 (a,\, b) als Kurzschreibweise für \operatorname{ggT}(a, b) verwendet.

Inhaltsverzeichnis

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:
\operatorname{ggT}(12, 18) = 6

Berechnung

Berechnung über die Primfaktorzerlegung

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

  • 3528 = 2^{\color{Red}3} \cdot 3^{\color{Red}2} \cdot 7^{\color{Red}2}
  • 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:

  • \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 wird durch den steinschen Algorithmus noch weiter verbessert.

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:

\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, b und m ganze Zahlen. Dann gilt:

\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 | a | den Betrag von a.

Aus der genannten Rechenregel \operatorname{ggT}(a, 0) = |a| ergibt sich speziell \operatorname{ggT}(0, 0)=0. Dies ergibt sich auch daraus, dass jede ganze Zahl m (sogar die 0 selbst) wegen m\cdot0=0 Teiler der 0 ist, während umgekehrt 0 keine von 0 verschiedene Zahl teilt.

Ist m \ne 0 ein gemeinsamer Teiler von a und b, dann gilt:

m   teilt   \operatorname{ggT}(a, b)   und
\operatorname{ggT}(a: m, b: m) = \operatorname{ggT}(a, b): |m|

Ist a \equiv b\ \bmod\ m   (a und b sind kongruent modulo m), dann gilt:

\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 a und b gilt

\operatorname{ggT}(a b, m) = \operatorname{ggT}(a, m) \cdot\operatorname{ggT}(b, m)

Lemma von Bézout

Hauptartikel: Lemma von Bézout

Nach dem Lemma von Bézout lässt sich der größte gemeinsame Teiler zweier ganzer Zahlen m und n als Linearkombination von m und n mit ganzzahligen Koeffizienten darstellen:

  • \operatorname{ggT}(m,n) = s \cdot m + t \cdot n mit s,t\in\mathbb{Z}

Beispielsweise besitzt der größte gemeinsame Teiler von 12 und 18 die folgende Darstellung:

  • \operatorname{ggT}(12,18) = 6 = (-1)\cdot 12 + 1\cdot 18

Die Koeffizienten s und 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. \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 \operatorname{ggT}(12, 18) = {\color{Blue} 6}, also

\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 a und b sind assoziiert, in Zeichen a \sim b, wenn es eine Einheit \epsilon \, mit  a = b \cdot \epsilon gibt.

Wir erweitern den Begriff des ggT auf die Menge aller größten gemeinsamen Teiler der Elemente einer Teilmenge M eines Ringes R, formal:

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: d teilt alle Elemente aus M und wird selbst von allen Elementen aus 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:

\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

\operatorname{ggT}(f, g) \sim X + Y

Der Polynomring \Q[X] in einer Variablen X ist euklidisch. Dort gibt es zur Berechnung des \operatorname{ggT} eine Division mit Rest.

Gaußscher Zahlenring

Im gaußschen Zahlenring \Z+\mathrm{i}\Z ist der größte gemeinsame Teiler von 2 und 1 + 3i gerade 1 + i, denn 2 = − i(1 + i)2 und 1 + 3i = (1 + i)(2 + i). Genau genommen ist 1 + i nur ein größter gemeinsamer Teiler, da alle zu dieser Zahl assoziierten Zahlen ebenfalls größte gemeinsame Teiler sind. (Die Einheiten sind \pm 1, \pm \mathrm{i}.)

Integritätsringe

Im Integritätsring 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 1 + \sqrt{-3} und 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 a und b.

Die genannten Elemente 1+\sqrt{-3} und 2 haben aber ihrerseits einen ggT, nämlich 1. Dagegen haben sie kein kgV, denn wenn v ein kgV wäre, dann folgt aus der „ggT-kgV-Gleichung“, dass v assoziiert zu k:=(1 + \sqrt{-3})\cdot2 sein muss. Das gemeinsame Vielfache 4 ist jedoch kein Vielfaches von k, also ist k kein kgV und die beiden Elemente haben gar kein kgV.

Ist R ein Integritätsring und haben die Elemente a und b ein kgV, dann haben sie auch einen ggT, und es gilt die Gleichung

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.

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

Siehe auch

Analytische Zahlentheorie

In der elementaren Zahlentheorie gehört der größte gemeinsame Teiler g von zwei ganzen Zahlen m,n\in\Z\setminus \lbrace 0 \rbrace zu den wichtigsten Grundkonzepten. Man schreibt dort regelmäßig g = (m,n) und meint damit dann den positiven ggT, geht also von g\in\N aus.

In der analytischen Zahlentheorie kann die ggT-Funktion \Z\setminus \lbrace 0 \rbrace \rightarrow \N;\;m\mapsto (m,n) in einer Variablen für festes n\in\N\setminus \lbrace 0 \rbrace analytisch zu einer ganzen Funktion fortgesetzt werden. → Siehe Ramanujansumme.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?
Synonyme:

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Größter Gemeinsamer Teiler — Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle. Der größte gemeinsame Teiler… …   Deutsch Wikipedia

  • größter gemeinsamer Teiler — g.g.T.; ggT * * * größter gemeinsamer Teiler,   Abkürzung g. g. T., die größte ganze positive Zahl, die zwei oder mehrere vorgegebene ganze Zahlen ohne Rest teilt: Der größte gemeinsame Teiler von 60 und 24 ist 12, der größte gemeinsame Teiler… …   Universal-Lexikon

  • Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches — Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle. Der größte gemeinsame Teiler… …   Deutsch Wikipedia

  • Gemeinsamer Teiler — Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle. Der größte gemeinsame Teiler… …   Deutsch Wikipedia

  • Teiler (Mathematik) — Teilbarkeit ist eine mathematische Beziehung zwischen zwei ganzen Zahlen. Eine ganze Zahl ist genau dann durch eine andere ganze Zahl teilbar, wenn bei der Division kein Rest verbleibt, also die „Geteilt Rechnung“ aufgeht. So ist beispielsweise… …   Deutsch Wikipedia

  • Teiler — Tei|ler 〈m. 3; Math.〉 ganze Zahl, die in einer anderen Zahl mehrmals ohne Rest enthalten ist * * * Tei|ler, der; s, (Math.): Divisor. * * * Teiler,   Mathematik: eine ganze Zahl a ∈ ℤ, die eine ganze Zahl c teilt (Symbol a …   Universal-Lexikon

  • Teiler — Tei|ler; größter gemeinsamer Teiler (Abkürzung g. g. T., ggT) …   Die deutsche Rechtschreibung

  • Gemeinsamer Nenner — ist in der deutschen Sprache eine Metapher für eine gemeinsame Vereinbarung oder Verabredung. Kleinster gemeinsamer Nenner Die Redewendung kleinster gemeinsamer Nenner kann kritisch einen Kompromiss auf niedrigstem Niveau, einen fragwürdigen… …   Deutsch Wikipedia

  • Kleinster gemeinsamer Nenner — Gemeinsamer Nenner ist in der deutschen Sprache eine Metapher für eine gemeinsame Vereinbarung oder Verabredung. Die Redewendung kleinster gemeinsamer Nenner kann kritisch einen Kompromiss auf niedrigstem Niveau, einen fragwürdigen Konsens… …   Deutsch Wikipedia

  • Nichttrivialer Teiler — Teilbarkeit ist eine mathematische Beziehung zwischen zwei ganzen Zahlen. Eine ganze Zahl ist genau dann durch eine andere ganze Zahl teilbar, wenn bei der Division kein Rest verbleibt, also die „Geteilt Rechnung“ aufgeht. So ist beispielsweise… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”