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 größte gemeinsame Teiler zweier ganzer Zahlen $m$ und $n$ ist die größte natürliche Zahl, durch die sowohl $m$ als auch $n$ ohne Rest teilbar sind. Für $m=n=0$ ist der größte gemeinsame Teiler nicht definiert; für die algebraische Definition gelten abweichende Eigenschaften.

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

Oft wird auch $(m,\,n)$ als Kurzschreibweise für $\operatorname {ggT} (m,n)$ 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:

$\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{aligned}1071&:1029&=\ &1&\ \operatorname {Rest} &\ 42\\1029&:42&=\ &24&\ \operatorname {Rest} &\ 21\\42&:21&=\ &2&\ \operatorname {Rest} &\ 0\end{aligned}}$

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

Rechenregeln

$a$ und $b$ seien ganze Zahlen und $m$ eine natürliche Zahl. Dann gilt:

${\begin{aligned}\operatorname {ggT} (a,b)&=\operatorname {ggT} (b,a)&{\text{(Kommutativgesetz)}}\\\operatorname {ggT} (-a,b)&=\operatorname {ggT} (a,b)\\\operatorname {ggT} (a,a)&=a&(a\neq 0)\\\operatorname {ggT} (a,0)&=a&(a\neq 0)\\\operatorname {ggT} (a,1)&=1\\\operatorname {ggT} (a,b)&=\operatorname {ggT} (b,a\;{\bmod {\;}}b)&(b>0)\\\operatorname {ggT} (a,b)&=\operatorname {ggT} (b,a-b)\\\operatorname {ggT} (ma,mb)&=m\cdot \operatorname {ggT} (a,b)&{\text{(Distributivgesetz)}}\\\operatorname {ggT} (a+mb,b)&=\operatorname {ggT} (a,b)\end{aligned}}$

Der größte gemeinsame Teiler $\operatorname {ggT} (0,0)$ ist nicht definiert, denn da jede Zahl 0 teilt, gibt es keine größte Zahl mit dieser Eigenschaft.

Ist $m$ ein gemeinsamer Teiler von $a$ und $b$, dann gilt:

$\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} (ab,m)=\operatorname {ggT} (a,m)\cdot \operatorname {ggT} (b,m)$

ggT von mehreren Zahlen

• $\operatorname {ggT} (m,\,\operatorname {ggT} (n,p))=\operatorname {ggT} (\operatorname {ggT} (m,n),\,p)=\operatorname {ggT} (m,n,p)$

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}}$

Anwendungen in weiteren algebraischen Strukturen

Der ggT lässt sich nicht nur für natürliche (und ganze) Zahlen definieren. Man kann ihn z. B. auch für Polynome bilden. Statt der Primfaktorzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren:

${\begin{aligned}f(x)&=x^{2}+2xy+y^{2}=(x+y)^{2}\\g(x)&=x^{2}-y^{2}=(x+y)(x-y)\end{aligned}}$

Dann ist

$\operatorname {ggT} (f,g)=x+y$

Möglich wird dies, da auch für Polynome eine Division mit Rest existiert.

Um den Begriff des größten gemeinsamen Teilers auf beliebige kommutative Ringe ausdehnen zu können, muss man die Definition ändern, da in beliebigen Ringen nicht vorausgesetzt werden kann, dass die Elemente bezüglich $<$ angeordnet werden können. Deshalb ersetzt man diese Anordnung durch die durch den Teilbarkeitsbegriff definierte partielle Ordnung.

Ist $d$ ein Ringelement, das sowohl Teiler von $a$ als auch Teiler von $b$ ist, dann heißt $d$ ein gemeinsamer Teiler von $a$ und $b$. Gilt zusätzlich, dass jeder weitere gemeinsame Teiler von $a$ und $b$ auch ein Teiler von $d$ ist, dann heißt $d$ ein größter gemeinsamer Teiler von $a$ und $b$. Solche größten gemeinsamen Teiler sind dann nicht mehr notwendigerweise eindeutig. Das Symbol $\operatorname {ggT} (M)$ für ein $M\subseteq R$ fasst man dann als die Menge der größten gemeinsamen Teiler der Elemente aus $M$ auf.

Formal schreibt man diese Definition für einen Ring $R$ etwa so:

$d\in \operatorname {ggT} (M)\quad :\Longleftrightarrow \quad \forall x\in M:d\mid x\land \left(\exists 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 Elemente aus $R$ geteilt, die vielleicht ebenfalls alle Elemente aus $M$ teilen.

Weil multiplikativ invertierbare Elemente, sogenannte Einheiten, den ersten Teil der Definition stets erfüllen, ist die Existenz solcher Elemente für allgemeine Mengen $M$ stets gesichert. Falls ein Element diese Definition erfüllt, tun es auch alle Elemente, die sich von diesem lediglich durch Multiplikation mit einer Einheit unterscheiden, seine Assoziierten.

Beispiele

2=82

Gaußscher Zahlenring

Im gaußschen Zahlenring $\mathbb {Z} +\mathrm {i} \mathbb {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$ ein größter gemeinsamer Teiler, da alle zu dieser Zahl assoziierten Zahlen ebenfalls größte gemeinsame Teiler sind.

Nicht in jedem Ring existiert für zwei Elemente ein ggT oder ein kgV. Wenn sie einen ggT haben, können sie mehrere ggT haben. Ist der Ring ein Integritätsring, dann sind alle ggT zueinander assoziiert.

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=\operatorname {ggT} (a,b)\cdot \operatorname {kgV} (a,b)$

Ist jedoch nur bekannt, dass ein ggT von $a$ und $b$ existiert, dann muss nicht unbedingt auch ein kgV existieren.

Integritätsring

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}})\cdot 2$ 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.

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 einem faktoriellen Ring haben je zwei Elemente einen ggT.

In einem euklidischen Ring lässt sich der ggT zweier Elemente mit dem euklidischen Algorithmus bestimmen.

Zusammenhang zwischen ggT und dem kleinsten gemeinsamen Vielfachen

→ siehe Kleinstes gemeinsames Vielfaches#Zusammenhang von kgV und ggT

Weblinks

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