Größter gemeinsamer Teiler

Der größte gemeinsame Teiler (ggT) ist die jeweils größte natürliche Zahl $m$, durch die sich zwei oder mehr gegebene ganze Zahlen ohne Rest teilen lassen. Weiterhin sind auch alle (echten) Teiler von $m$ dann Teiler aller beteiligten Zahlen, aber nicht die größten Teiler. Ist der größte gemeinsame Teiler $1$, sind die beteiligten Zahlen teilerfremd. In der elementaren Mathematik ist dessen wichtigste Anwendungen das Kürzen von Brüchen.

So ist der $\operatorname {ggT} (10,\ 15)=5$, da sich sowohl $10$ und $15$ durch $5$ teilen lassen. Der Bruch ${\tfrac {10}{15}}$ lässt sich zu ${\tfrac {2}{3}}$ kürzen. Die beiden „verbleibenden“ Zahlen $2$ und $3$ sind nun teilerfremd und lassen sich nicht weiter kürzen.

Sein Pendant ist das kleinste gemeinsame Vielfache (kgV). Beide spielen unter anderem in der Arithmetik, der Algebra und der Zahlentheorie eine Rolle.

Wichtigste Anwendung ist heutzutage die Kryptografie.

Das Konzept des größten gemeinsamen Teilers lässt sich auf Gaußsche Zahlen, Polynome, Funktionen und vieles andere erweitern.

Definition

Der größte gemeinsame Teiler ggT zweier ganzen Zahlen $a$ und $b$, von denen mindestens eine ungleich Null ist, ist die größte ganze Zahl $m$, so dass $m$ ein Teiler sowohl von $a$ als auch von $b$ ist. Das heißt, es gibt ganze Zahlen $e$ und $f$, so dass

$a=m\cdot e$ und $b=m\cdot f$

ist, und $m$ ist die größte Zahl mit dieser Eigenschaft.

Als Operator wird er $\operatorname {ggT} (a,\ b)$ in deutschen Texten, $\operatorname {gcd} (a,\ b)$ (greatest common divider) in englischen Texten geschrieben, wobei letztere Schreibweise auch in deutschen Texten zu finden ist.

Ist eine der beiden Zahlen $a$ und $b$ Null, so ist der ggT der absolute Wert der betragsmäßig größeren Zahl:

$\operatorname {ggT} (0,\ a)=\operatorname {max} (|0|,\ |a|)=\operatorname {max} (0,\ |a|)=|a|$,

da $|a|\geq 0$ ist und was auch mit $0=|a|\cdot 0$ und $a=|a|\cdot \operatorname {sgn} (a)$ übereinstimmt, wobei $\operatorname {sgn} (a)$ hier für $+1$ für positive und $-1$für negative Zahlen steht. Dieser Fall ist weiterhin wichtig für den Abschluss des euklidischen Algorithmus.

Sind beide Zahlen Null, so ergibt letztere Regel

$\operatorname {ggT} (0,\ 0)=\operatorname {max} (|0|,\ |0|)=\operatorname {max} (0,\ 0)=0$,

was wiederum mit $0=0\cdot 0$ und $0=0\cdot 0$ übereinstimmt, auch wenn die Zahl $0$ mit dem Namen größter gemeinsamer Teiler nicht harmonisiert.

Diese Definition bzw. Konvention wird meist auch verwendet, da sie einige Konzepte vereinfacht (wie z. B. die Bézout-Identität). Auch die meisten Computeralgebrasysteme, wie z. B. Wolfram Alpha benutzen diese Definition. Einige Autoren lassen $\operatorname {ggT} (0,\ 0)$ jedoch ähnlich wie ${\tfrac {0}{0}}$ undefiniert.

Der ggT von $a$ und $b$ ist ihr größter gemeinsamer positiver Teiler in der Quasiordnung der Teilbarkeit. Das bedeutet, dass die gemeinsamen Teiler von $a$ und $b$ genau die Teiler ihres ggT sind. Dies wird in der Regel mit Hilfe des Lemma von Euklid, des Fundamentalsatzes der Arithmetik oder des euklidischen Algorithmus bewiesen. Dies ist die Bedeutung von „größte“, die für die Verallgemeinerungen des Konzepts des ggT verwendet wird. Dies spielt eine wesentliche Rolle, wenn man die Schulmathematik verlässt und nicht nur Zahlen, sondern komplexere mathematische Konzepte wie Polynome, Funktionen und Matrizen verwendet.

Beispiele

Größter gemeinsamer Teiler zweier Zahlen

$\operatorname {ggT} (12,\ 18)$

• $12$ hat die Teiler: $1,2,3,4,6,\ \ \ 12$.
• $18$ hat die Teiler: $1,2,3,\ \ ,6,9,\ \ \ 18$.
• Die gemeinsamen Teiler von $12$ und $18$ sind: $1,2,3$ und $6$.

Der größte gemeinsamen Teiler ist $6$:

$\operatorname {ggT} (12,\ 18)=6$

Größter gemeinsamer Teiler dreier Zahlen

$\operatorname {ggT} (12,\ 18,\ 30)$

• $12$ hat die Teiler: $1,2,3,4\ \ ,6,\ \ \ \ 12$.
• $18$ hat die Teiler: $1,2,3,\ \ \ \ ,6,9,\ \ \ \ \ \ \ 18$.
• $30$ hat die Teiler: $1,2,3,\ \ 5,6,\ 10,\ 15,\ \ 30$.
• Die gemeinsamen Teiler von $12$, $18$ und $30$ sind: $1,2,3$ und $6$.

Der größte gemeinsamen Teiler ist $6$:

$\operatorname {ggT} (12,18,30)=6$

Größter gemeinsamer Teiler zweier Polynome

$\operatorname {ggT} (2x^{3}+9x^{2}+6x+1,\ 3x^{3}+14x^{2}+11x+2)$

• $2x^{3}+\ \ 9x^{2}+\ \ 6x+1$ hat die Teiler: $\;2x+1$ und $x^{2}+4x+1$.
• $3x^{3}+14x^{2}+11x+2$ hat die Teiler: $\;3x+2$ und $x^{2}+4x+1$.
• $x^{2}+4x+1\;$ lässt sich als $\;(x+2-{\sqrt {3}})\cdot (x+2+{\sqrt {3}})$ darstellen.
• Die gemeinsamen Teiler von $\ 2x^{3}+9x^{2}+6x+1\$ und $\ 3x^{3}+14x^{2}+11x+2\$ sind:

$1$, $\;x+2-{\sqrt {3}}$, $\;x+2+{\sqrt {3}}\$ und $\;x^{2}+4x+1$.

Der größte gemeinsamen Teiler ist $x^{2}+4x+1$

$\operatorname {ggT} (2x^{3}+9x^{2}+6x+1,\ 3x^{3}+14x^{2}+11x+2)=x^{2}+4x+1$.

Größter gemeinsamer Teiler zweier Funktionen

$\operatorname {ggT} ((x^{2}-1)f(x),\ (x+1)g(x))$

• $(x^{2}-1)f(x)$ hat die Teiler: $x+1$, $\;x-1$ und $f(x)$.
• $(x\ +\ 1)g(x)$ hat die Teiler: $x+1$ und $g(x)$.
• Die gemeinsamen Teiler von $(x^{2}-1)f(x)$ und $(x+1)g(x)$ sind: $x+1$

$\operatorname {ggT} ((x^{2}-1)f(x),\ (x+1)g(x))=x+1$.

Rechenregeln

Für ganze Zahlen $a,b,c,k$ gilt – mit $|a|$ als dem Betrag von $a$:

	●	$\operatorname {ggT} (a,b)$	$=\operatorname {ggT} (b,a)$	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)$	$=\operatorname {ggT} (a,b\;{\bmod {\;}}a)=\operatorname {ggT} (a\;{\bmod {\;}}b,b)$	für $a,b\neq 0$
	●	$\operatorname {ggT} (a,b+ac)$	$=\operatorname {ggT} (a,b)$
	●	$\operatorname {ggT} (a,b)$	$=\operatorname {ggT} (b-a,b)$	mindestens für $0\leq a\leq b$
	●	$\operatorname {ggT} (a,b,c)$	$=\operatorname {ggT} (a,\,\operatorname {ggT} (b,c))=\operatorname {ggT} (\operatorname {ggT} (a,b),\,c)\qquad$	Assoziativgesetz
	●	$\operatorname {ggT} (a)$	$=|a|$
	●	$\operatorname {ggT} (a,\ b,\ c,\ \ldots )$	$=\operatorname {ggT} (a,\,\operatorname {ggT} (b,\ c,\ \ldots )$
	●	$\operatorname {ggT} (k\cdot a,k\cdot b)$	$=|k|\cdot \operatorname {ggT} (a,b)$	Distributivgesetz
	●	$\operatorname {ggT} (a,b)\!\cdot \!\operatorname {kgV} (a,b)$	$=ab$	Verhältnis zwischen ggT und kgV
	●	Ist $k$ ein gemeinsamer Teiler von $a$ und $b$, dann gilt: $k$   teilt   $\operatorname {ggT} (a,b)$   und     $\operatorname {ggT} (a/k,b/k)\,=\operatorname {ggT} (a,b)/|k|$		für $k\neq 0$
	●	Ist $a\equiv b\ {\bmod {\ }}c$   ($a$ und $b$ sind kongruent modulo $c$), dann gilt:     $\operatorname {ggT} (a,c)\qquad \;\;\,=\operatorname {ggT} (b,c)$

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 $a$ (sogar die 0 selbst) wegen $a\cdot 0=0$ Teiler der 0 ist, während umgekehrt 0 keine von 0 verschiedene Zahl teilt.

Hält man eines der beiden Argumente fest, dann ist $\operatorname {ggT}$ eine multiplikative Funktion, denn für teilerfremde Zahlen $a$ und $b$ gilt:

$\operatorname {ggT} (ab,c)=\operatorname {ggT} (a,c)\cdot \operatorname {ggT} (b,c)$

Berechnung des größten gemeinsamen Teilers zwei Zahlen

Berechnung über die Primfaktorzerlegung

Man kann den $\operatorname {ggT}$ über die Primfaktorzerlegung der beiden gegebenen Zahlen bestimmen.

Beispiel

• $3528=2^{\color {Red}3}\cdot 3^{\color {Red}2}\cdot 5^{\color {Red}0}\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 $\operatorname {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 5^{\color {Red}0}\cdot 7^{\color {OliveGreen}1}=252$

Euklidischer Algorithmus

→ Hauptartikel: Euklidischer Algorithmus

Die Berechnung der Primfaktorzerlegung großer Zahlen und damit auch die Bestimmung des größten gemeinsamen Teilers über die Primfaktorzerlegungen ist sehr aufwändig. Mit dem euklidischen Algorithmus existiert jedoch auch ein effizientes Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen.

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 mehrfach abgezogen, bis ein Ergebnis übrig bleibt, das kleiner als die kleinere ist (erste zwei Schritte im Beispiel). Bei einer Differenz von 0 ist man fertig und die kleinere Länge das Ergebnis. Andernfalls wiederholt man dieses Abziehen – jetzt aber mit der kleineren Länge anstelle der größeren und der letzten Differenz anstelle der kleineren Länge (im Beispiel die Schritte drei bis sieben mit dem Rest 13 als der kleineren Länge und 65 als der jetzt größeren). Beispiel für den größten gemeinsamen Teiler von 143 und 65:

${\begin{aligned}143-65&=78\\78-65&=13&(<65)\\65-13&=52\\52-13&=39\\39-13&=26\\26-13&=13\\13-13&=\,\;0&(<13)\end{aligned}}$

Der größte gemeinsame Teiler von 143 und 65 ist somit 13.

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

${\begin{aligned}3780&/3528&=\ &\ \ 1&\ \operatorname {Rest} &\ 252\\3528&/\ \ 252&=\ &14&\ \operatorname {Rest} &\ 0\\\end{aligned}}$

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

In der Programmiersprache C kann der Algorithmus wie folgt programmiert werden:

int GroessterGemeinsamerTeiler (int a, int b)
{
    if (a == 0) return abs(b);
    if (b == 0) return abs(a);

    do {
        int h = a % b;
        a = b;
        b = h;
    } while (b != 0);

    return abs(a);
}

Eine Variante mit Rekursion ist wie folgt formuliert:

int GroessterGemeinsamerTeiler (int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;
    return GroessterGemeinsamerTeiler (b, a % b);
}

Steinscher Algorithmus

Der steinsche Algorithmus ist eine Variation des euklidischen Algorithmus. Ob er eine Verbesserung darstellt, hängt von der jeweiligen Bewertungsfunktion und „Maschinerie“ ab, die den jeweiligen Algorithmus ausführt.

Der ggT von mehreren Zahlen

Man verwendet alle Primfaktoren, die in jeder der Zahlen vorkommen, mit der jeweils kleinsten vorkommenden Potenz, zum Beispiel:

$144=2^{\color {Red}4}\cdot 3^{\color {Red}2}\cdot 5^{\color {Red}0}\cdot 7^{\color {Red}0}$

$160=2^{\color {OliveGreen}5}\cdot 3^{\color {OliveGreen}0}\cdot 5^{\color {OliveGreen}1}\cdot 7^{\color {OliveGreen}0}$

$175=2^{\color {Blue}0}\cdot 3^{\color {Blue}0}\cdot 5^{\color {Blue}2}\cdot 7^{\color {Blue}1},$

also:

$\operatorname {ggT} (144,160,175)=2^{\color {Blue}0}\cdot 3^{\color {OliveGreen}0}\cdot 5^{\color {Red}0}\cdot 7^{\color {Red}0}=1.$

Man könnte auch zunächst $\operatorname {ggT} (144,160)=16$ berechnen und danach $\operatorname {ggT} (16,175)=1,$ denn als eine zweistellige Verknüpfung auf den natürlichen Zahlen ist der $\operatorname {ggT}$ assoziativ:

$\operatorname {ggT} (m,\,\operatorname {ggT} (n,o))=\operatorname {ggT} (\operatorname {ggT} (m,n),\,o).$

Dies rechtfertigt die Schreibweise $\operatorname {ggT} (m,n,o)$.

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.

Sonderfälle

Für gerades $e$, ungerades $d$ sowie ganzes $i,j,k$ gilt:

$\operatorname {ggT} (2e,e^{2}-1)=1$;

$\operatorname {ggT} (2d,d^{2}-1)=2$;

$\operatorname {ggT} (2k(k+1),2k+1)=1$;

$\operatorname {ggT} (4k,4k^{2}-1)=1$;

$\operatorname {ggT} (i-j,1+i+j)=\operatorname {ggT} (1+2j,1+2i)$;

$\operatorname {ggT} (a,b)=2\operatorname {ggT} (a/2,b/2)$, falls $a$ und $b$ gerade.

$\operatorname {ggT} (a,b)=\operatorname {ggT} (a/2,b)$, falls $a$ gerade und $b$ ungerade.

$\operatorname {ggT} (a,b)=\operatorname {ggT} ((a-b)/2,b)$, falls $a$ und $b$ ungerade.

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

Aus $p=a+b,\ 0<b\leq a<p,\ a\in \mathbb {N} ,b\in \mathbb {N} ,\ p\in \mathbb {P}$ folgt $\operatorname {ggT} (a,b)=1$.

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

Ein Bruch mit Zähler $a$ und Nenner $b$, bei dem $\operatorname {ggT} (a,b)=1$ ist, ist nicht weiter kürzbar. Er wird voll gekürzt oder auch vollständig oder maximal gekürzter Bruch genannt.

Zusammenhang zwischen ggT und dem kleinsten gemeinsamen Vielfachen

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

Beweis: Nachweis für positive ganze Zahlen $m$ und $n$, alle anderen Fälle lassen sich analog behandeln. Sei $k=\operatorname {kgV} (m,n)$, dann ist $k$ auch Teiler des Produkts $m\cdot n$. Die Zahl $g$ enthalte dagegen alle Primfaktoren des Produkts $m\cdot n$, die $k$ nicht enthält. Betrachtet man, wie der $\operatorname {ggT} (m,n)$ aus der Primfaktordarstellung des Produkts aus $m$ und $n$ berechnet wird, dann folgt $g=\operatorname {ggT} (m,n)$. Daraus ergibt sich die obige Gleichung.

Weitere algebraische Strukturen mit ggT

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

Ein Integritätsring, in dem je zwei Elemente einen $\operatorname {ggT}$ besitzen, heißt ggT-Ring oder ggT-Bereich. (In einem $\operatorname {ggT}$-Ring haben je zwei Elemente auch ein $\operatorname {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 $\operatorname {ggT}$ gegebenenfalls 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 $\operatorname {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 \forall y\in R:(\forall x\in M:y\mid x)\Leftrightarrow y\mid d$.

In Worten: Die Teiler von $d$ sind genau die Elemente aus $R$, die alle Elemente aus $M$ teilen. Die $\operatorname {ggT}$ sind untereinander assoziiert.

Polynomringe

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

${\begin{aligned}f(X,Y)&=X^{2}+2XY+Y^{2}=(X+Y)^{2}\\g(X,Y)&=X^{2}-Y^{2}=(X+Y)(X-Y)\end{aligned}}$

Dann ist

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

Der Polynomring $\mathbb {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 $\mathbb {Z} +\mathrm {i} \mathbb {Z}$ ist der größte gemeinsame Teiler von $2$ und $1+3\mathrm {i}$ gerade $1+\mathrm {i}$, denn $2=-\mathrm {i} (1+\mathrm {i} )^{2}$ und $1+3\mathrm {i} =(1+\mathrm {i} )(2+\mathrm {i} )$. Genau genommen ist $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 $\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 $\operatorname {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 $\operatorname {ggT}$ von $a$ und $b$.

Die genannten Elemente $1+{\sqrt {-3}}$ und $2$ haben aber ihrerseits einen $\operatorname {ggT}$, nämlich $1$. Dagegen haben sie kein $\operatorname {kgV}$, denn wenn $v$ ein $\operatorname {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 $\operatorname {kgV}$ und die beiden Elemente haben gar kein $\operatorname {kgV}$.

Ist $R$ ein Integritätsring und haben die Elemente $a$ und $b$ ein $\operatorname {kgV}$, dann haben sie auch einen $\operatorname {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. 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 Zahlentheorie

In der elementaren Zahlentheorie gehört der größte gemeinsame Teiler $t$ von zwei ganzen Zahlen $m,n\in \mathbb {Z} \setminus \lbrace 0\rbrace$ zu den wichtigsten Grundkonzepten. Man schreibt dort regelmäßig $t=(m,n)$ und meint damit dann den positiven $\operatorname {ggT}$, geht also von $t\in \mathbb {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 $n\in \mathbb {N} \setminus \lbrace 0\rbrace$ analytisch zu einer ganzen Funktion fortgesetzt werden. → Siehe Ramanujansumme.

Literatur

• Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8.
• Universität Ulm: Elementare Zahlentheorie.

Weblinks

Wikibooks: Algorithmensammlung – Euklidischer Algorithmus und ggT – Lern- und Lehrmaterialien

• Verschiedene Online-Tools zur Primfaktorzerlegung, ggT und kgV.
• Skriptum: (PDF; 1,0 MB) Analytische Fortsetzung des ggT zu einer ganzen Funktion.
• Christian Spannagel: Der Euklidische Algorithmus. Vorlesungsreihe, 2012.
• Christian Spannagel: Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache. Vorlesungsreihe, 2012.