Quelltext der Seite Größter gemeinsamer Teiler

Der '''größte gemeinsame Teiler''' ('''ggT''') ist ein [[Mathematik|mathematischer]] Begriff. Sein Pendant ist das ''[[Kleinstes gemeinsames Vielfaches|kleinste gemeinsame Vielfache]] (kgV)''. Beide spielen unter anderem in der [[Arithmetik]] und der [[Zahlentheorie]] eine Rolle.

Er ist die größte [[natürliche Zahl]], durch die sich zwei [[Ganze Zahl|ganze Zahlen]] ohne [[Division mit Rest|Rest]] teilen lassen. Der <math>\operatorname{ggT}</math> zweier [[Ganze Zahl|ganzer Zahlen]] <math>a</math> und <math>b</math> ist eine ganze Zahl <math>m</math> mit der Eigenschaft, dass sie [[Teilbarkeit|Teiler]] sowohl von <math>a</math> als auch von <math>b</math> ist und dass jede ganze Zahl, die ebenfalls die Zahlen <math>a</math> und <math>b</math> teilt, ihrerseits Teiler von <math>m</math> ist.<ref>''Schüler-Duden: Die Mathematik I.'' Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 167</ref> Beim [[Ring (Algebra)|Ring]] <math>\Z</math> der ganzen Zahlen (der eine [[Totalordnung]] > besitzt) normiert man den <math>\operatorname{ggT}</math> auf die größte ganze solche Zahl <math>|m|</math>.

Der Begriff „groß“ in <math>\operatorname{ggT}</math> korreliert hochgradig mit der üblichen [[Ordnungsrelation]] > der ganzen Zahlen. Es gibt allerdings eine wichtige Ausnahme: Da die <math>0</math> [[Vielfaches]] einer jeden ganzen Zahl <math>m</math> ist, ist <math>0</math> in Teilbarkeitsfragen an „Größe“ nicht zu überbieten. Diese Auffassung ist in Einklang mit der [[Teilbarkeit#Teilbarkeit als Verband|Verbandsvorstellung]] (und der [[Ideal (Ringtheorie)|Idealtheorie]]) und vereinfacht einige der unten aufgeführten Rechenregeln.

Die englische Bezeichnung '''gcd''' ''(greatest common divisor)'' für <math>\operatorname{ggT}</math> ist in mathematischen Texten ebenfalls verbreitet.<ref>Calvin T. Long: ''Elementary Introduction to Number Theory'', D. C. Heath and Company, Boston, 1972, ISBN 978-0669627039, S. 33</ref>

Oft wird auch <math>(a,\, b)</math> als Kurzschreibweise für <math>\operatorname{ggT}(a, b)</math> verwendet.<ref>Peter Bundschuh: ''Einführung in die Zahlentheorie''. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8, S. 15.</ref>

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

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

* <math>3528 = 2^{\color{Red}3} \cdot 3^{\color{Red}2} \cdot 5^{\color{Red}0} \cdot 7^{\color{Red}2}</math>
* <math>3780= 2^{\color{OliveGreen}2} \cdot 3^{\color{OliveGreen}3} \cdot 5^{\color{OliveGreen}1} \cdot 7^{\color{OliveGreen}1}</math>

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

* <math>\operatorname{ggT}(3528,3780) = 2^{\color{OliveGreen}2} \cdot 3^{\color{Red}2} \cdot 5^{\color{Red}0}  \cdot 7^{\color{OliveGreen}1} = 252</math><ref>''Schüler-Duden: Die Mathematik I.'' Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 354</ref>

=== 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 [[Euklidischer Algorithmus|euklidischen Algorithmus]] existiert jedoch ein [[Effizienz (Informatik)|effizientes]] Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen. Dieses Verfahren wurde durch den [[Steinscher Algorithmus|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.

Der klassische euklidische Algorithmus berechnet den größten gemeinsamen Teiler, indem er nach einem gemeinsamen „Maß“ für die Längen zweier Linien sucht.<ref>Lambacher-Schweizer: ''Mathematik für Gymnasien 5 Niedersachsen''. Klett Verlag, Stuttgart 2006, ISBN 978-3-12-734551-3, S. 197.</ref> 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:

<math>\begin{align}
143 - 65 &= 78\\
78 - 65 &= 13 &(<65)\\
65 - 13 &= 52\\
52 - 13 &= 39\\
39 - 13 &= 26\\
26 - 13 &= 13\\
13- 13 &= \, \;0 &(< 13)
\end{align}</math>

Der größte gemeinsame Teiler von 143 und 65 ist somit 13. Wenn man weiß, dass 13 prim ist, könnte man im Beispiel schon im zweiten Schritt den Teiler ablesen, da eine Primzahl als Ergebnis nicht weiter geteilt werden kann.

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:

<math>\begin{align}
3780 &: 3528 &= \ &1 &\ \operatorname{Rest} &\ 252\\
3528 &: 252 &= \ &14 &\ \operatorname{Rest} &\ 0\\
\end{align}</math>

Somit ist 252 der größte gemeinsame Teiler von 3780 und 3528.<ref>''Schüler-Duden: Die Mathematik I.'' Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 100</ref>

In [[C (Programmiersprache)|C]] wird der Algorithmus wie folgt formuliert:

<syntaxhighlight lang="C">
int GreatestCommonDivisor(int a, int b)
{
    int h;
    if (a == 0) return abs(b);
    if (b == 0) return abs(a);

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

    return abs(a);
}
</syntaxhighlight>

== Der ggT von mehreren Zahlen ==
{{Anker|ggT von mehreren Zahlen}}

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

:<math>144 = 2^{\color{Red}4} \cdot 3^{\color{Red}2} \cdot 5^{\color{Red}0} \cdot 7^{\color{Red}0}</math>
:<math>160= 2^{\color{OliveGreen}5} \cdot 3^{\color{OliveGreen}0} \cdot 5^{\color{OliveGreen}1} \cdot 7^{\color{OliveGreen}0}</math>
:<math>175= 2^{\color{Blue}0} \cdot 3^{\color{Blue}0} \cdot 5^{\color{Blue}2} \cdot 7^{\color{Blue}1},</math>

also:

:<math>\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.</math><ref>''Schüler-Duden: Die Mathematik I.'' Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 168</ref>

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

:<math>\operatorname{ggT}(m,\,\operatorname{ggT}(n,o)) = \operatorname{ggT}(\operatorname{ggT}(m,n),\,o).</math>

Dies rechtfertigt die Schreibweise <math> \operatorname{ggT}(m,n,o)</math>.<ref>Harald Scheid: ''Einführung in die Zahlentheorie.'' Klett Verlag, Stuttgart, 1972, ISBN 3-12-983240-8, S. 78.</ref>

== Rechenregeln ==
Für ganze Zahlen <math>a, b, c</math> gilt – mit <math>|a|</math> als dem [[Betragsfunktion|Betrag]] von <math>a</math>:
{|
|-
|style="width:0.1em"| ||style="width:0.7em"| <small>&#x25CF;</small> ||style="width:9em"| <math>\operatorname{ggT}(a, b)</math> ||style="width:22em"| <math>= \operatorname{ggT}(b, a)</math> || (Kommutativgesetz)
|-
| || <small>&#x25CF;</small> || <math>\operatorname{ggT}(\pm a, \pm b)</math> || <math>= \operatorname{ggT}(a, b)</math>
|-
| || <small>&#x25CF;</small> || <math>\operatorname{ggT}(a, a)</math> || <math>= |a|</math>
|-
| || <small>&#x25CF;</small> || <math>\operatorname{ggT}(a, 0)</math> || <math>= |a|</math>
|-
| || <small>&#x25CF;</small> || <math>\operatorname{ggT}(a, 1)</math> || <math>= 1</math>
|-
| || <small>&#x25CF;</small> || <math>\operatorname{ggT}(a, b \;\bmod\; a)</math> || <math>= \operatorname{ggT}(a,b) </math> || <math>(a \ne 0)</math>
|-
| || <small>&#x25CF;</small> || <math>\operatorname{ggT}(a, b + a c)</math> || <math>= \operatorname{ggT}(a, b)</math>
|-
| || <small>&#x25CF;</small> || <math>\operatorname{ggT}(a,b,c)</math> || <math>= \operatorname{ggT}(a,\,\operatorname{ggT}(b,c)) = \operatorname{ggT}(\operatorname{ggT}(a,b),\,c)</math> || (Assoziativgesetz)
|-
| || <small>&#x25CF;</small> || <math>\operatorname{ggT}(a \cdot c, b \cdot c)</math> || <math>= \operatorname{ggT}(a, b) \cdot |c|</math> || (Distributivgesetz)
|-
| ||style="vertical-align:top"| <small>&#x25CF;</small> ||colspan="2"| Ist <math>c </math> ein gemeinsamer Teiler von <math>a</math> und <math>b</math>, dann gilt:<br /><math>c</math> &nbsp; teilt &nbsp; <math>\operatorname{ggT}(a, b)</math> &nbsp; und<br /> &nbsp; &nbsp; <math>\operatorname{ggT}(a: c, b: c) \, = \operatorname{ggT}(a, b): |c|</math> ||style="vertical-align:bottom"| für &nbsp; <math>c \ne 0 .</math>
|-
| ||style="vertical-align:top"| <small>&#x25CF;</small> ||colspan="3"| Ist <math>a \equiv b\ \bmod\ c</math> &nbsp; (<math>a</math> und <math>b</math> [[Kongruenz (Zahlentheorie)|sind kongruent modulo]] <math>c</math>), dann gilt:<br /> &nbsp; &nbsp; <math>\operatorname{ggT}(a, c) \qquad \; \; \, = \operatorname{ggT}(b, c)</math>
|}
Aus der genannten Rechenregel <math>\operatorname{ggT}(a, 0) = |a|</math> ergibt sich speziell <math>\operatorname{ggT}(0, 0)=0</math>. Dies ergibt sich auch daraus, dass jede ganze Zahl <math>a</math> (sogar die 0 selbst) wegen <math>a\cdot0=0</math> Teiler der 0 ist, während umgekehrt 0 keine von 0 verschiedene Zahl teilt.

Hält man eines der beiden Argumente fest, dann ist <math>\operatorname{ggT}</math> eine [[Zahlentheoretische Funktion|multiplikative Funktion]], denn für [[teilerfremd]]e Zahlen <math>a</math> und <math>b</math> gilt:
:<math>\operatorname{ggT}(a b, c) = \operatorname{ggT}(a, c) \cdot\operatorname{ggT}(b, c)</math>

== 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 <math>m</math> und <math>n</math> als [[Linearkombination]] von <math>m</math> und <math>n</math> mit ganzzahligen Koeffizienten darstellen:
* <math>\operatorname{ggT}(m,n) = s \cdot m + t \cdot n</math> mit <math>s,t\in\mathbb{Z}</math><ref>[https://www.inf.hs-flensburg.de/lang/krypto/algo/euklid-erweitert.htm Lemma von Bézout]</ref>

Beispielsweise besitzt der größte gemeinsame Teiler von <math>12</math> und <math>18</math> die folgende Darstellung:
* <math>\operatorname{ggT}(12,18) = 6 = (-1)\cdot 12 + 1\cdot 18</math>

Die Koeffizienten <math>s</math> und <math>t</math> können mit dem [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] berechnet werden.

== Sonderfälle ==
Für gerades <math>e</math>, ungerades <math>d</math> sowie ganzes <math>i,j,k</math> gilt:
:<math>\operatorname{ggT}(2e, e^2-1) = 1</math>;
:<math>\operatorname{ggT}(2d, d^2-1) = 2</math>;
:<math>\operatorname{ggT}(2k(k+1), 2k+1) = 1</math>;
:<math>\operatorname{ggT}(4k, 4k^2-1) = 1</math>;
:<math>\operatorname{ggT}(i-j, 1+i+j) = \operatorname{ggT}(1+2j, 1+2i)</math>;
:<math>\operatorname{ggT}(a, b) = 2 \operatorname{ggT}(a/2, b/2)</math>, falls a und b gerade.
:<math>\operatorname{ggT}(a, b) = \operatorname{ggT}(a/2, b)</math>, falls a gerade und b ungerade.
:<math>\operatorname{ggT}(a, b) = \operatorname{ggT}((a-b)/2,b)</math>, falls a und b ungerade.

Setzt man eine Primzahl aus zwei echten Summanden zusammen, gilt für diese stets Teilerfremdheit:
: <math>p=a+b; 0<b\le a<p; a,b\in \N, p\in \mathbb P; ggT(a,b)=1</math>.

== Anwendungen ==
=== Bruchrechnung ===
Beim [[Kürzen]] wird ein gemeinsamer [[Multiplikation|Faktor]] von Zähler und Nenner eines Bruches entfernt, wobei sich der Wert des Bruches nicht ändert, z.&nbsp;B. <math>\tfrac{12}{18} = \tfrac{6 \cdot 2}{9 \cdot 2} = \tfrac{6}{9}</math>. Kürzt man mit dem größten gemeinsamen Teiler von Zähler und Nenner, entsteht ein Bruch, der nicht weiter kürzbar ist.<ref>L. Engelmann (Hrsg.): ''Kleiner Leitfaden Mathematik'', Paetec, Berlin 1997, ISBN 3-89517-150-6, S. 51/2</ref> Zum Beispiel ist <math>\operatorname{ggT}(12, 18) = {\color{Blue} 6}</math>, also
: <math>\frac{12}{18} = \frac{2 \cdot {\color{Blue} 6}}{3 \cdot {\color{Blue} 6}} = \frac{2}{3}</math>

{{Anker|gekürzter Bruch}}Ein Bruch mit Zähler a und Nenner b, bei dem ggT(a,b) =1 ist, ist nicht weiter kürzbar. Er wird ''voll gekürzt''<ref>Schüler-Duden: Die Mathematik I, Dudenverlag, Mannheim. Leipzig, Wien, Zürich 1990, ISBN 3-411-04205-2, S. 48</ref> oder auch ''vollständig'' oder ''maximal gekürzter Bruch'' genannt.

=== Zusammenhang zwischen ''ggT'' und dem ''kleinsten gemeinsamen Vielfachen'' ===
<math>\mathrm{ggT}(a, b) \cdot \mathrm{kgV}(a, b) = a \cdot b</math>

Beweis: Nachweis für positive ganze Zahlen m und n, alle anderen Fälle lassen sich analog behandeln. Sei <math>k = \operatorname{kgV}(m,n)</math>, dann ist <math>k</math> auch Teiler des Produkts <math>m \cdot n</math>. Die Zahl <math>g</math> enthalte dagegen alle Primfaktoren des Produkts <math>m \cdot n</math>, die <math>k</math> nicht enthält. Betrachtet man, wie der <math>\operatorname {ggT}(m,n)</math> aus der Primfaktordarstellung des Produkts aus <math>m</math> und <math>n</math> berechnet wird, dann folgt <math>g = \operatorname{ggT}(m,n)</math>. Daraus ergibt sich die obige Gleichung.<ref>[http://math-www.uni-paderborn.de/~chris/Index37/V/par4.pdf math-www.uni-paderborn.de], S. 14 ggT und kgV</ref>

== Weitere algebraische 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 [[Nullteiler|nullteilerfreie]] Ringe, im kommutativen Fall sind das die [[Integritätsring]]e.

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 [[antisymmetrische Relation|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 [[Assoziierte Elemente|Assoziiertheit]] bestimmen. Zwei Elemente <math>a</math> und <math>b</math> sind assoziiert, in Zeichen <math>a \sim b</math>, wenn es eine [[Einheit (Mathematik)|Einheit]] <math>\epsilon</math> mit <math> a = b \cdot \epsilon</math> gibt.

Wir erweitern den Begriff des ggT auf die Menge aller größten gemeinsamen Teiler der Elemente einer Teilmenge <math>M</math> eines Ringes <math>R</math>, formal:
:<math>d \in \operatorname{ggT}(M)\quad:\Longleftrightarrow\quad \forall y\in R: (\forall x\in M: y\mid x)\Leftrightarrow y\mid d</math>.
In Worten: Die Teiler von <math>d</math> sind genau die Elemente aus <math>R</math>, die alle Elemente aus <math>M</math> teilen.
Die ggT sind untereinander assoziiert.

=== Polynomringe ===
Man kann den ggT z. B. auch für [[Polynom]]e bilden. Statt der [[Primfaktorzerlegung]] nimmt man hier die Zerlegung in [[Irreduzibles Polynom|irreduzible]] Faktoren:

:<math>\begin{align}
f(X,Y) &= X^2 + 2XY + Y^2 = (X + Y)^2\\
g(X,Y) &= X^2 - Y^2 = (X + Y) (X - Y)
\end{align}</math>

Dann ist
:<math>\operatorname{ggT}(f, g) \sim X + Y</math>

Der [[Polynomring]] <math>\Q[X]</math> in einer Variablen <math>X</math> ist [[Euklidischer Ring|euklidisch]]. Dort gibt es zur Berechnung des <math>\operatorname{ggT}</math> eine [[Division mit Rest]].

=== Gaußscher Zahlenring ===
Im [[Gaußsche Zahl|gaußschen Zahlenring]] <math>\Z+\mathrm{i}\Z</math> ist der größte gemeinsame Teiler von <math>2</math> und <math>1 + 3\mathrm{i}</math> gerade <math>1 + \mathrm{i}</math>, denn <math>2 = -\mathrm{i} (1 + \mathrm{i})^2</math> und <math>1 + 3\mathrm{i} = (1 + \mathrm{i}) (2 + \mathrm{i})</math>. Genau genommen ist <math>1 + \mathrm{i}</math> nur ''ein'' größter gemeinsamer Teiler, da alle zu dieser Zahl assoziierten Zahlen ebenfalls größte gemeinsame Teiler sind. (Die Einheiten sind <math>\pm 1, \pm \mathrm{i}</math>.)

=== Integritätsringe ===
Im [[Integritätsring]] <math>R = \mathbb{Z}[\sqrt{-3}]</math> haben die Elemente
:<math>a:= 4 = 2\cdot 2 = (1 + \sqrt{-3})(1 - \sqrt{-3}),\quad b:= (1 + \sqrt{-3})\cdot 2</math>

keinen ggT: Die Elemente <math>1 + \sqrt{-3}</math> und <math>2</math> sind zwei ''maximale gemeinsame Teiler'', denn beide haben den gleichen [[Betragsfunktion#Komplexe Betragsfunktion|Betrag]], aber diese zwei Elemente sind nicht zueinander assoziiert. Also gibt es keinen ggT von <math>a</math> und <math>b</math>.

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

Ist <math>R</math> ein Integritätsring und haben die Elemente <math>a</math> und <math>b</math> ein kgV, dann haben sie auch einen ggT, und es gilt die Gleichung
:<math>a \cdot b \sim \operatorname{ggT}(a, b) \cdot \operatorname{kgV}(a, b)</math>

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 [[Hurwitzquaternion#größter gemeinsamer Teiler|Hurwitzquaternionen]].

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

In der [[Analytische Zahlentheorie|analytischen Zahlentheorie]] kann die ggT-Funktion <math>\Z\setminus \lbrace 0 \rbrace \rightarrow \N;\;m\mapsto (m,n)</math> in ''einer'' Variablen für festes <math>n\in\N\setminus \lbrace 0 \rbrace</math> [[Analytische Fortsetzung|analytisch]] zu einer [[Ganze Funktion|ganzen Funktion]] fortgesetzt werden. → Siehe [[Ramanujansumme]].

== Einzelnachweise ==
<references />

== Literatur ==
* [[Peter Bundschuh]]: ''Einführung in die Zahlentheorie''. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8.
* Universität Ulm: "Elementare Zahlentheorie" [https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.zawa/lehre/11elzahl/Skript.pdf]

== Weblinks ==
{{Wikibooks|Algorithmensammlung: Zahlentheorie: Euklidischer Algorithmus|Algorithmensammlung - Euklidischer Algorithmus und ggT}}
* [http://www.openwebschool.de/06/ma/ Verschiedene Online-Tools] zur Primfaktorzerlegung, ggT und kgV.
* [http://www.schramm.cc/download/GGT.pdf Skriptum:] (PDF; 1,0&nbsp;MB) Analytische Fortsetzung des ggT zu einer ganzen Funktion.
* [[Christian Spannagel]]: [https://av.tib.eu/series/232/ Der Euklidische Algorithmus]. Vorlesungsreihe, 2012.
* [[Christian Spannagel]]: [https://av.tib.eu/series/243/ Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache]. Vorlesungsreihe, 2012.

{{DEFAULTSORT:Grosster Gemeinsamer Teiler}}
[[Kategorie:Arithmetik]]
[[Kategorie:Zahlentheorie]]