Quelltext der Seite größter gemeinsamer Teiler

Der '''größte gemeinsame Teiler (ggT)''' ist die jeweils größte [[natürliche Zahl]] <math>m</math>, durch die sich zwei oder mehr gegebene [[ganze Zahl]]en ohne [[Division mit Rest|Rest]] teilen lassen. Weiterhin sind auch alle (echten) Teiler von <math>m</math> dann Teiler aller beteiligten Zahlen, aber nicht die größten Teiler. Ist der größte gemeinsame Teiler <math>1</math>, sind die beteiligten Zahlen [[Teilerfremdheit|teilerfremd]]. In der elementaren Mathematik ist dessen wichtigste Anwendung das Kürzen von Brüchen.

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

Sein Pendant ist das ''[[Kleinstes gemeinsames Vielfaches|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 Zahl]]en, [[Polynom]]e und vieles andere erweitern.

== Definition ==
Der größte gemeinsame [[Teilbarkeit|Teiler]] '''ggT''' zweier [[Ganze Zahl|ganzen Zahlen]] <math>a</math> und <math>b</math>, von denen mindestens eine ungleich Null ist, ist die größte ganze Zahl <math>m</math>, so dass <math>m</math> ein Teiler sowohl von <math>a</math> als auch von <math>b</math> ist. Das heißt, es gibt ganze Zahlen <math>\alpha</math> und <math>\beta</math>, so dass
: <math>a = m \cdot \alpha\quad</math> und <math>\quad b = m \cdot \beta</math>
ist und <math>m</math> die größte Zahl mit dieser Eigenschaft ist.

Als Operator wird er <math>\operatorname{ggT}(a,\ b)</math> in deutschsprachigen Texten, <math>\operatorname{gcd}(a,\ b)</math> (greatest common divisor) in englischsprachigen Texten geschrieben, wobei letztere Schreibweise auch in deutschsprachigen Texten zu finden ist. Eine weitere Bezeichnung ist ''greatest common factor''.

Ist eine der beiden Zahlen <math>a</math> und <math>b</math> Null, so ist der ggT der absolute Wert der betragsmäßig größeren Zahl:
: <math>\operatorname{ggT}(0,\ a) = \operatorname{max}(|0|,\ |a|) = \operatorname{max}(0,\ |a|) = |a|</math>,

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

Sind beide Zahlen Null, so ergibt letztere Regel
: <math>\operatorname{ggT}(0,\ 0) = \operatorname{max}(|0|,\ |0|) = \operatorname{max}(0,\ 0) = 0</math>,

was wiederum mit <math>0 = 0 \cdot 0</math> und <math>0 = 0 \cdot 0</math> übereinstimmt, auch wenn die Zahl <math>0</math> mit dem Begriff ''größter gemeinsamer '''Teiler''''' nicht harmonisiert (obwohl es für den ggT gar keiner Division bedarf, siehe Definition).

Diese Definition bzw. Konvention wird meist auch verwendet, da sie einige Konzepte vereinfacht (wie z.&#8239;B. die Bézout-Identität). Auch die meisten [[Computeralgebrasystem]]e, wie z.&#8239;B. [[Wolfram Alpha]] benutzen diese Definition. Einige Autoren lassen <math>\operatorname{ggT}(0,\ 0)</math> jedoch ähnlich wie <math>\tfrac{0}{0}</math> undefiniert.

Der ggT von <math>a</math> und <math>b</math> ist ihr größter gemeinsamer positiver Teiler in der [[Quasiordnung]] der Teilbarkeit. Das bedeutet, dass die gemeinsamen Teiler von <math>a</math> und <math>b</math> genau die Teiler ihres ggT sind. Dies wird in der Regel mit Hilfe des [[Lemma von Euklid]], des [[Fundamentalsatz der Arithmetik|Fundamentalsatzes der Arithmetik]] oder des [[euklidischer Algorithmus|euklidischen Algorithmus]] bewiesen. Dies ist die Bedeutung von „größte“, die für die Verallgemeinerung 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 ===
<math>\operatorname{ggT}(12,\ 18)</math><ref>[https://www.wolframalpha.com/input?i=gcd+%2812%2C+18%29 Wolfram Alpha zu ggT(12, 18)]</ref>
* <math>12</math> hat die Teiler: <math>1, 2, 3, 4   , 6,\ \ \ 12</math>.
* <math>18</math> hat die Teiler: <math>1, 2, 3, \ \ , 6, 9,\ \ \  18</math>.
* Die gemeinsamen Teiler von <math>12</math> und <math>18</math> sind: <math>1, 2, 3</math> und <math>6</math>.
: Der größte gemeinsame Teiler ist <math>6</math>:
::<math>\operatorname{ggT}(12,\ 18) = 6</math>

=== Größter gemeinsamer Teiler dreier Zahlen ===
<math>\operatorname{ggT}(12,\ 18,\ 30)</math><ref>[https://www.wolframalpha.com/input?i=gcd+%2812%2C+18%2C+30%29 Wolfram Alpha zu ggT(12, 18, 30)]</ref>
* <math>12</math> hat die Teiler: <math>1, 2, 3, 4   \ \ , 6,\ \ \ \ 12</math>.
* <math>18</math> hat die Teiler: <math>1, 2, 3, \ \ \ \ , 6, 9,\ \ \ \ \ \ \ 18</math>.
* <math>30</math> hat die Teiler: <math>1, 2, 3, \ \ 5   , 6, \ 10,\ 15,\ \  30</math>.
* Die gemeinsamen Teiler von <math>12</math>, <math>18</math> und <math>30</math> sind:  <math>1, 2, 3</math> und <math>6</math>.
: Der größte gemeinsame Teiler ist <math>6</math>:
::<math>\operatorname{ggT}(12, 18, 30) = 6</math>

=== Größter gemeinsamer Teiler zweier Polynome ===
Die „Größe“ wird hier gemessen im [[Polynomgrad]].

;Im [[Ring (Algebra)|Ring]] <math>\Z[x]</math>:
: <math>\operatorname{ggT}(x^2-1,\ x+1)</math>:
:* <math>x^2-1</math> hat die Teiler <math>x+1</math>, <math>\;x-1</math>. Beide haben den Grad 1.
:* <math>x\ +\ 1</math> hat den Teiler <math>x+1</math>.
:Ergebnis: Der gradmäßig größte gemeinsame Teiler von <math>x^2-1</math> und <math>x+1</math> ist <math>\;x+1</math>.
:<math>\qquad\qquad\Longrightarrow \operatorname{ggT}(x^2-1,\ x+1) = x+1</math>.

:<math>\operatorname{ggT}(2 x^3 + 9 x^2 + 6 x + 1,\ 3 x^3 + 14 x^2 + 11 x + 2)</math><ref>[https://www.wolframalpha.com/input?i=gcd+%282+x%5E3+%2B+9+x%5E2+%2B+6+x+%2B+1%2C+3+x%5E3+%2B+14+x%5E2+%2B+11+x+%2B+2%29 Wolfram Alpha zu ggT(2''x''³ + 9''x''² + 6''x'' + 1, 3''x''³ + 14''x''² + 11''x'' + 2)]</ref>
:* <math>2 x^3 + \ \ 9 x^2 + \ \ 6 x + 1</math> hat die Teiler <math>\;2x + 1</math> und <math>x^2 + 4x + 1</math>.
:* <math>3 x^3 +    14 x^2 + 1   1 x + 2</math> hat die Teiler <math>\;3x + 2</math> und <math>x^2 + 4x + 1</math>.
:* <math>x^2 + 4x + 1\;</math> lässt sich zwar darstellen als <math>\;(x + 2 - \sqrt{3}) \cdot (x + 2 + \sqrt{3})</math>. Wegen <math>\sqrt{3} \notin \Z</math> ist es aber [[Primelement|prim]] im Ring <math>\Z[x]</math>.
:* Die gemeinsamen Teiler von <math>\ 2 x^3 + 9 x^2 + 6 x + 1\ </math> und <math>\ 3 x^3 + 14 x^2 + 11 x + 2\ </math> sind im Ring <math>\Z[x]</math>:
::: <math>1\;</math> und <math>\;x^2 + 4x + 1</math>.
:Ergebnis: Der gradmäßig größte gemeinsame Teiler ist: <math>\;x^2 + 4x + 1</math>
:<math>\qquad\qquad\Longrightarrow \operatorname{ggT}(2 x^3 + 9 x^2 + 6 x + 1,\ 3 x^3 + 14 x^2 + 11 x + 2) = x^2 + 4x + 1</math>.

;Im Ring <math>\Q(\sqrt{3})[x]</math>:
:Die gemeinsamen Teiler von <math>\ 2 x^3 + 9 x^2 + 6 x + 1\ </math> und <math>\ 3 x^3 + 14 x^2 + 11 x + 2\ </math> sind wegen
:* <math>x^2 + 4x + 1\; = \;(x + 2 - \sqrt{3}) \cdot (x + 2 + \sqrt{3})</math>
:* <math>1</math>, <math>\;x + 2 - \sqrt{3}</math>, <math>\;x + 2 + \sqrt{3}\ </math> und <math>\;x^2 + 4x + 1</math>.
:Ergebnis: Der größte gemeinsame Teiler im Ring <math>\Q(\sqrt{3})[x]</math> ist: <math>\;x^2 + 4x + 1</math>
:<math>\qquad\qquad\Longrightarrow\operatorname{ggT}(2 x^3 + 9 x^2 + 6 x + 1,\ 3 x^3 + 14 x^2 + 11 x + 2) = x^2 + 4x + 1</math>.

;Im Ring <math>\R[x]</math>:
* <math>\operatorname{ggT}(\pi x^2-\pi,\ x+1) = x+1</math>.
<!-- <ref>[https://www.wolframalpha.com/input?i=gcd+%28%28x%5E2-1%29+f%28x%29%2C+%28x%2B1%29+g%28x%29%29 Wolfram Alpha zu ggT((''x''^2−1) ''f''(''x''), (''x''+1) ''g''(''x''))]</ref>-->

== Rechenregeln für Zahlen ==
Für ganze Zahlen <math>a,\ b,\ c,\ k</math> und <math>|a|</math> als dem [[Betragsfunktion|Betrag]] von <math>a\,</math> gilt:
{|
| style="width:7px" |
|| <small>●</small> || <math>\operatorname{ggT}(a,\ b)</math>               || <math>= \operatorname{ggT}(b, a)</math>                                                     || [[Kommutativgesetz]]
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ b,\ c)</math>              || <math>= \operatorname{ggT}(a,\,\operatorname{ggT}(b,c)) = \operatorname{ggT}(\operatorname{ggT}(a,b),\,c)\qquad</math> || [[Assoziativgesetz]]
|-
| || <small>●</small> || <math>\operatorname{ggT}(k \cdot a,\ k \cdot b)</math>|| <math>= |k| \cdot \operatorname{ggT}(a,\ b)</math>                                     || [[Distributivgesetz]]
|-
| || <small>●</small> || <math>\operatorname{ggT}(\pm a, \pm b)</math>       || <math>= \operatorname{ggT}(a,\ b)</math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ 0)</math>              || <math>= |a|</math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ 1)</math>              || <math>= 1</math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ a)</math>              || <math>= |a|</math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ b)</math>              || <math>= \operatorname{ggT}(a,\ b \bmod a) \;=\; \operatorname{ggT}(a \bmod b,\ b) </math> || für <math>a,b \ne 0</math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ b + a c)</math>        || <math>= \operatorname{ggT}(a,\ b)</math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ b)</math>              || <math>= \operatorname{ggT}(b-a,\ b)</math>  || mindestens für <math> 0 \le a \le b </math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a)</math>                  || <math>= |a|</math> 
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ b,\ c,\ \ldots)</math> || <math>= \operatorname{ggT}(a,\,\operatorname{ggT}(b,\ c,\ \ldots))</math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a_1\!\ldots\!a_n,b_1\!\ldots\!b_m)</math> || <math>= \operatorname{ggT}(\operatorname{ggT}(a_1,\ldots a_n),\ \operatorname{ggT}(b_1,\ldots b_m))</math>
|-
| || <small>●</small> || <math>\operatorname{ggT}(a,\ b) \cdot \operatorname{kgV}(a,\ b) </math> || <math> = |ab|</math>                                                 || Verhältnis zwischen ggT und kgV
|-
| || style="vertical-align:top"| <small>●</small> 
|colspan="2"| Ist <math>k </math> ein gemeinsamer Teiler von <math>a</math> und <math>b</math>, dann gilt:<br /> <math>\qquad k</math> &nbsp; teilt &nbsp; <math>\operatorname{ggT}(a, b)</math> &nbsp; und<br /> <math>\qquad \operatorname{ggT}\Big(\tfrac{a}{k},\ \tfrac{b}{k}\Big) \qquad = \tfrac{\operatorname{ggT}(a,\ b)}{|k|}</math> 
|style="vertical-align:bottom"| für <math>k \ne 0</math>
|-
| || style="vertical-align:top"| <small>●</small> 
|colspan="2"| 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 /> <math>\qquad \operatorname{ggT}(a,\ c) \qquad \quad = \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\cdot 0 = 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 [[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>

== Berechnung des größten gemeinsamen Teilers ==
=== Berechnung mittels Primfaktorzerlegung ===
Für die Berechnung mittels Primfaktorzerlegung zweier Zahlen <math>a</math> und <math>b</math> verwendet man alle Primfaktoren, die in jeder der beiden Zahlen vorkommen, mit der jeweils kleinsten vorkommenden Potenz.

Gegeben seien die Primfaktorzerlegungen:
:<math> a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot\;\cdots \;\cdot p_m^{\alpha_m} </math>
:<math>\, b = p_1^{\beta_1} \cdot p_2^{\beta_2} \cdot\;\cdots \;\cdot p_m^{\beta_m} </math>

mit <math>\alpha_j</math> resp. <math>\beta_j</math> als den Exponenten des Primfaktors <math>p_j</math> der Zahl <math>a</math> resp. der Zahl <math>b</math> (für {{Zeile|<math>j = 1, \ldots, m</math>).}} Da beide, <math>a</math> und <math>b</math>, ganze Zahlen sind, sind alle diese Exponenten <math>\ge 0</math>.

Der <math>\operatorname{ggT}(a,\ b)</math> berechnet sich zu
:<math>\operatorname{ggT}(a,\ b) = \prod_{j=1}^m p_j^{\min(\alpha_j,\ \beta_j)}</math>
mit <math>\,\min(\alpha_j,\ \beta_j)</math> als dem <abbr style="cursor:default" title="genauer: dem Minimum">kleinsten</abbr> Exponenten des Primfaktors <math>p_j</math> beider Zahlen.

;Beispiel:
Gesucht ist der größte gemeinsame Teiler von <math>2970</math> und <math>12\,936</math>.

Die beiden Primfaktorzerlegungen lauten:

* <math> \, \,\, 2970 \, = 2^{\color{Red }1} \cdot 3^{\color{Gray}3} \cdot 5^{\color{Gray}1} \cdot 7^{\color{Red }0} \cdot 11^{\color{Red}1}</math>
* <math>12\,936  = 2^{\color{Gray}3} \cdot 3^{\color{Red }1} \cdot 5^{\color{Red }0} \cdot 7^{\color{Gray}2} \cdot 11^{\color{Red}1}</math>
Dabei sind die jeweils kleinsten Exponenten in Rot, die anderen (irrelevanten) in Grau gesetzt.

Die jeweils kleinsten Exponenten sind <math>({\color{Red }1},\ {\color{Red }1},\ {\color{Red }0},\ {\color{Red }0},\ {\color{Red }1})</math>. Daher folgt:

:<math>\operatorname{ggT}(2970,\ 12\,936) = 2^{\color{Red}1} \cdot 3^{\color{Red}1} \cdot 5^{\color{Red}0} \cdot 7^{\color{Red}0} \cdot 11^{\color{Red}1} = 2 \cdot 3 \cdot 1 \cdot 1 \cdot 11 = 66.</math>

=== 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 bis hin zu [[NP (Komplexitätsklasse)|praktisch unmöglich]]. Allerdings benötigt man auch gar nicht die Primfaktoren der beteiligten Zahlen, um den ggT zu bestimmen. Mit dem [[Euklidischer Algorithmus|euklidischen Algorithmus]] existiert ein [[Effizienz (Informatik)|effizientes]] Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen. So braucht man von <math>1\,000\,000\,004\,147</math> und <math>1\,000\,000\,004\,149</math> gar nicht die Primfaktoren zu kennen, um zu erkennen, dass der <math>\operatorname{ggT}(1\,000\,000\,004\,147,\ 1\,000\,000\,004\,149) = 1</math> ist. Über die Primfaktoren-Zerlegung wäre das eine Lebensaufgabe, mit dem euklidischen Algorithmus ist das Ergebnis sofort zu sehen.

Der klassische euklidische Algorithmus (wie von Euklid vor 2300 Jahren beschrieben) 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&nbsp;– 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{array}{rl|l}
143 - 65 & =    78 \\
 78 - 65 & =    13 & \scriptstyle\text{ Die entstandene Differenz 13 ist nun kleiner als der Subtrahend 65, die beiden Zahlen werden getauscht.} \\ 
 65 - 13 & =    52 \\
 52 - 13 & =    39 \\
 39 - 13 & =    26 \\
 26 - 13 & =    13 \\
 13 - 13 & = \ \ 0 & \scriptstyle\text{ Die entstandene Differenz ist 0, der letzte Minuend ist das Ergebnis.} \\ 
\end{array}</math>

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 143 und 65:

:<math>\begin{array}{rl|l}
   143 \,\,/\,\, 65 & =  \,\,\,  2 & \scriptstyle\text{ Rest 13} \\
\ \ 65 \,\,/\,\, 13 & =  \,\,\,  5 & \scriptstyle\text{ Rest  0: Der letzte Divisor 13 ist das Ergebnis.} \\
\end{array}</math>

Somit ist 13 der größte gemeinsame Teiler von 143 und 65.<ref>''Schüler-Duden: Die Mathematik I.'' Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 100</ref>
Beide Verfahren sind auch kombinierbar, bei kleineren Unterschieden kann man Subtrahieren, bei größeren die Division/Modulo-Operation verwenden.

In der Programmiersprache [[C (Programmiersprache)|C]] kann der Algorithmus für zwei vorzeichenlose 64-Bit-Ganzzahlen wie folgt formuliert werden:

<syntaxhighlight lang="C">
#include <stdint.h>

uint64_t ggT_Div_Schleife (uint64_t a, uint64_t b)
{
    if (a == 0) return b;
    if (b == 0) return a;

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

    return a;
}
</syntaxhighlight>

Eine Variante mit [[Rekursion]] (genauer: [[Endrekursion]]) lässt sich so formulieren:

<syntaxhighlight lang="c">
uint64_t ggT_Div_Rekursiv (uint64_t a, uint64_t b)
{
    if (a == 0) return b;
    if (b == 0) return a;
    return ggT_Div_Rekursiv (b, a % b);
}
</syntaxhighlight>

Beide Versionen erzeugen mit Optimierung durch Auflösung der Endrekursion identischen Code.<ref>[https://godbolt.org/z/bzo7zKqjj Compiler Explorer]</ref>

=== Steinscher Algorithmus ===
Neben dem euklidischen Algorithmus mit Modulo-Operation (bekanntere Version) und dem euklidischen Algorithmus mit rekursiver Subtraktion (ursprüngliche Version von Euklid) gibt es den [[Steinscher Algorithmus|steinschen Algorithmus]] als clevere Modifikation des euklidischen Algorithmus mit rekursiver Subtraktion.

Auf aktuellen CPUs<ref>C++, Microsoft Compiler, 64 bit-Code, Prozessoren um das Jahr 2020, Intel Cannon Lake, Raptor Lake, AMD ZEN 3, ZEN 4</ref> läuft der steinsche Algorithmus etwa dreimal langsamer als der euklidische Algorithmus mit Modulo-Operation.

Er vermeidet Divisionen und erkauft sich das durch viele schlecht vorhersagbare Sprünge. Erstere sind auf aktuellen CPUs mittlerweile relativ schnell (64-Bit-Ganzzahl- wie auch -Gleitkomma-Division: 14 ± 1 Takte Latenz), letztere bremsen aktuelle CPUs massiv aus (falsch vorhergesagter Sprung: 18 ± 3 Straftakte Latenz).

Im Gegensatz zum euklidischen Algorithmus mit rekursiver Subtraktion zeigt er nicht dessen [[Asymptote|asymptotisch]] extrem lange Laufzeiten im Worst-Case-Fall, wenn irgendwann bei der rekursiven Berechnung Operanden mit sehr unterschiedlicher Größe entstehen (die zur quasi endlosen rekursiven Subtraktions-Schleifen führen, siehe Kommentare).

Der Knuth-Algorithmus ist der von [[Donald E. Knuth]] optimierte Algorithmus auf heutige CPUs angewendet.

Das gemessene Laufzeitverhalten zeigt die folgende Tabelle. Die verwendete Implementierung des ggT der Code darunter. Alle vier Implementierungen liefern die gleichen numerischen Ergebnisse für <math>a,b > 0</math>.

{| class="wikitable" style="text-align:center"
|+ Ausführungszeiten in Nanosekunden für gleichverteilte Argumente (1 … 2<sup>n</sup> − 1)<ref>AMD Ryzen 9 3900X, Microsoft VC 2022, Optionen /GL /O2</ref><ref>[https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXAMx8BBAKoBnTAAUAHpwAMvAFYTStJg1DIApACYAQuYukl9ZATwDKjdAGFUtAK4sGISQCcpK4AMngMmAByPgBGmMT%2BpAAOqAqETgwe3r7%2BQSlpjgJhEdEscQnSdpgOGUIETMQEWT5%2BgbaY9oUMdQ0ExVGx8YkK9Y3NOW0jvf2l5f4AlLaoXsTI7BzmkuHI3lgA1CaSbsgj%2BIKH2CYaAIKb27uYB0cxhBd77x/vAPRfe1QmbkkJgsbmIe1OIBQy0ExAA%2BgAveKoK63MxbBg7Lz7Q5uMTAEiEBAsN57H5/AFAkFgiEgBQAdyYSRRKK8aSMey8ADYACxPAAiHPCBB5sIIhysNxZPL2dUw4QgXN5TFIHOlMXmzIA7BLrp88FQ9hAYoc%2BSaNPM9sRMAQVgw9kxxSi9QajeZOVwNTdPp8rTbiHamE83Ca9jEngAxGUEOUMCDK0MAWiYFpAUZjRpVTAT6vFBy9H19tvtbq4EbT8vjxskl2rHr2qdlFYuFy4KqrNewdYAVHszI7JZrTZKboq9tgvABrWh4dCwoReGIK6Xx0c5gc6z50hB0R5xvZgMAhte673vfWGwNvdX2vYJo%2B50m/ADqjADB2wfYAHAETNcLKG9gweIbxMD8TG/X9dRiFV0CYLx4gIPZ8EwJQ9muVl/kBYE3AQYgvHZWgKV/bkjHiR4AC05QIAA6J1Tz2DpUNPMM70kAUHUkf9Hz2ABJFhwWQBBpxYFgRkYPZwzEWhDTkHjIgAFRFABZa4AA0VTrNhcLIvYEHwrBGj2AApJhtNo/N3kLf1i04rUh1uEdpXHKcZ1hPk8AANyXJUVVXT1bm1OjLOtIsw0OSNnOnWd3K86CQLMABWUMUxsnUTEHZkbimRxkA5Bg0mACJ0D2WgBGAPYPHwghKOIVJvL2VQLW46dMCoBDySwqkGv3Q82L2DQkLwR5lFSdIBCQlC9gYIb0GIPBgDEu1gBQ614WjO0LEIBQVUwylQW6k0QwGvARiQhQ9gANXiBAxHWvY8GIK16A8wwxXXFEyUtELrJpNAqrhRFaogRqH3osHwfBslg0sawzA0IK8oKoqSrKr6xU4%2BsQFhTbhFEBhwxIBliHQaUIDdNGVRBjGrLtX1xTJJS8GQWqFFQKhEIuoQPt%2BNGi1hWEYi8OhHAYWEqCoBRaFoYGLQTPYuFBiGlbBskAHEGC8CqVTcAwjBVDpaGQZAVR4wQOnuo2VQYDzjb2eF5uhqwYYHezRwAaQ1ggEHqlc1X89KNw%2Bc890OvqBvS4NNTcADQ4Fc1vl%2BKgpPOmNJqAsE4hnR5rmIYAfEYaN%2BvBcJ0FIBGfW%2Bt8I9DRWE/u07YPOwwDOz3P88EQCDKLxux1zzAYmmhRMpPd58KRzBitK9k0HyxDcpDSrBBqurLyj5L%2BxHkDq2bPrF%2BqpEFDjDVbIspDUAOQLT8%2BMLt9vgU9%2BXw%2BcxPzfnQvJ5sGSvNX/oml6UZC8bZj7/jJB5BCcEFCCUeBdBoeAmAxHoAwGCrBCChjlDKBcBBiBMAnF0PYE4YwHCwgENw5QDBeANNlAgNAGBYDtBOQwDBy4fBYiGDigd3jpQFFuHchpn4cN5tZS8RwcR7FMC/Lhw87gYgeEGU4ThqIIGbJKNE9wsSPBxE%2BEuqA6QKEUcohy1wyRCBCkkPYXtHgazKMBNmewkhMAeudIg5iUJvVRFsKgtDWp7EiJEZkaIsA0MeL4j4XAwAcA0JE8JkT4YqMkK4fUw9spM1VLyLsM9TqqFLCGbyXZ5iQhYFJVAyAICfi7L44BKJkm5VHOkgQmSzD8kNIqPJBSiklLKRUjeKI%2BRPgAPIACUBRPjktcZQPE9jyVcY0iAIRlAXT6TxPk/tL6b1HPOfiR0N6fF6YMgUBBsl9UhKra08kmYTj3hASpp8hR7G0E0%2BGL9Pj8DBBAJ4/5jmnPOZci0oiDkHEsHsSQGhomRNzNoaw1h/KfADsw0e0o5w%2BAeds%2BiLzDS3LwMijGmLRG%2BNzHgSFlhoVK0RZsmGRyQCRVcjFQ0WSTAJU2vSvklM%2BwMoJQlZZKLTwbKaaSrlF97I7P6UM8xjSQyfIIGc5AFzoQECufyyEVAkhzUEC6U48QyAAr7IlKWxVzAJU5NRLgBp8qGhijOX5iVgD0rcEwswZgVQbJVBAAgZgEwHPmF2DQ1FIlcC7FwTAAQvi%2BK%2BNoZ16BlgIMwPMLpTyCyV36t0jKw5ri7JFSMyIYyJlTJGKWWZ8zFmcveqfdZSKtlxveGm/ZhyBQSqlTKqq8qK33Q7vc8tAi0VvNzHW75sqrlBnMdkwFwLQWPP/BCmGRKEawqvh8UcpKsUCOeSQdFHccVh3xQOvF2LCUWGJRDBdkKKVUtnPOMMwMFZsqZSy%2BljKOXXJ/u8HlIY%2BXNskafKtoqmk9ulT8hVIAlUquoYadVj0VTmG1QlXVAKDVGpNedCAZ6sGWoStahKtqIOOp8M6117qPRep9RoP1Aag0hrDYaCNC56AxsiA%2Biufo7RjrssPT9Gas2TNcQNfNCylkrIEaWzZG7m2fv%2BeKkAJzJW9sbXRoOrbF0I07e8zGEn60/IHaJ4dIKIlgoxhOp2e7p2rLBvO59Qml0fE7Rixd90t1%2BJ3ZOgzs7TyHvJbWkAjY7QXtvey5lDVWV3s5c2z4pmBSvoEe%2BzeImxUUpU1JwQTaBGKuVUKNVBADKaog/q6D%2BrDXGqmghjzKG0MYftVhlgOG3UeoI76/1gbg2RFDeGyN1HY0CJpomiRybDGsdGeMjjIxJCGjmTxotAV%2BPShCx1gRIma3Ka%2Bb%2BvtMmzxyfbQpldXaMY/obfF35RxB0Av/CO7TY67m7v3Rfcz8LeSHrM3Cv462rPtps7iuz/4CUOfO2DFzVgKUey8F7Wll6As3qvfe/lwWy19TC4ZwVHwovfvE/N7bcqluY0AylkDaWNXgftVl2gerEq5fg4aP7Xsis2rtQ6jB5XDS4aq96mrJH6uNYo816NrWEbtaYy7JJ9QcqpL2AM2h8ri2b2qQL1QTSuBom5Aa/lkv6U1gFArkRe2pDy4OAlJXB1b6fz2JqDXiuQwq%2BDGrg3zb2uqCTfZFEtzCnyj42t15j2zPPb29ut7Z3DOXYakDnzTShfoAS3d1Q/n/chkDwl5W0eyRqleDcT6nxQ/eaZVLg7hpI%2BWs5P1VQ4Y8/hnCfngvHAi/ALJNyT8oZ49GJ5knsPqeQxDv/BATPALs8aFz/nwv%2BfgHejJJIRpLw3Ewq6wjAAEtcSIfIQifwQOgW9De2Le7u5CUEmAmDRnktpJgxUIAaylkkLBGkgyiLhiqHNBANBWy8Afo//Vr%2B3%2BIIsFfIA18b8wFvq0O/DT79oIfzVhypu0cZ%2B/WByD%2Bf%2Bd%2BV%2BU0N%2BEBT%2BZcTmmMb%2Bm%2B2%2Bu%2Bv%2B/%2Bx%2BOIp%2BUBF%2BVOaBkB4B/%2Bz%2BCBq%2BX%2ByBX%2BqBMB6B8sJ%2Be2IBF%2B0g0Bj%2BKoUBeBcBMO/6T4DiBABMxASkN%2BjgSQ9AfSMQ2g1QBACG3IKoc%2B5%2BAycg2AJskQ4YckPE8k2AqOXO1uKIHAiwtAnACUvAfgESvAqAnAjs1g4IywqwGiaIPApABAmg2hiwE4IAFe1EmoXACUiUAQRGn4kg0uAQCU%2BgnA3IBhDhpAJhHAvACgIAV%2B9hRhiwcAsASAaALASQO4ZAFAEAKRaR9ACQNsSQSQsIHkXAAQsIBg0YIwsIqgPIfAws8Q0RRoYRLwzAxAAAnpwLYc0Q0K0cIaIQ4B0bwCkWwIIH0gwLQO0UYaQFgILMALiFLNEdwLwFgIUkYOIJMfgFaDUGAgsVoMEKoNUP9usLYUKB0GEdODENgm0R4FgAMXYXNCwLcWAsQDEKkJgHyJgCscANOEYA4YsFQAYAtBdENHSH0kkIwLcfwIICIGIOwFwJIZCfIEoGoGEboK2LrMYLuvoHgDENEZAIsKgIfhkAsQmH0mYMYU8XNFgLiVcu0J0BkC4LQuMH4K2KEOEAMNYgkK2PkGNJkJ4C0HoNyV0DMIMJybSWIbUKME0HyTkK2FUDUAID0I0MKRyXoFMGMNKcybYJKcqXMB6EsCsGsBIDoXoaEZMREQ1NKKJDbHsMUQENROUa4oaLgIQCupsB6LwHEVoPME4SAAlFwNRGYJ%2BNyJqNyBoAEJ%2BFwJyJ%2BJqBoIEboRwCEaQA8VwJEqQIYbsREVETEXYb8caRwGSWmWEZmTmfEYsE8WkM4NyEAA Compiler Explorer]</ref>
!rowspan="2"| Zahlen-<br>paare !!colspan="4"| ggT(64 bit, 64 bit) !!colspan="4"| ggT(64 bit, 48 bit) !!colspan="4"| ggT(64 bit, 32 bit)
|- style="line-height:120%; font-size:90%"
! Euklid<br>(Div) || Knuth || Stein || Euklid<br>(Sub)
! Euklid<br>(Div) || Knuth || Stein || Euklid<br>(Sub)
! Euklid<br>(Div) || Knuth || Stein || Euklid<br>(Sub)
|-
| 10<sup>3</sup> || 142 || 122 || 462 || {{0}}591 ||  111 || 113 || 345 || 307 · 10<sup>3</sup> ||  76 || 105 || 317 || {{0}}5,0 · 10<sup>9</sup> 
|-
| 10<sup>4</sup> || 142 || 122 || 387 ||     1024 ||  111 || 113 || 352 || 495 · 10<sup>3</sup> ||  78 || 105 || 322 || 11,9 · 10<sup>9</sup>
|-
| 10<sup>5</sup> || 142 || 122 || 382 || {{0}}800 ||  111 || 113 || 348 || 729 · 10<sup>3</sup> ||  78 || 106 || 322 || zu lang<sup>*)</sup>
|-
| 10<sup>6</sup> || 142 || 122 || 379 || {{0}}843 ||  111 || 114 || 351 || 520 · 10<sup>3</sup> ||  78 || 106 || 325 || zu lang<sup>*)</sup>
|-
| 10<sup>7</sup> || 142 || 122 || 380 ||     1754 ||  111 || 113 || 336 || zu lang<sup>*)</sup> ||  78 || 106 || 322 || zu lang<sup>*)</sup>
|}
<sup>*)</sup> Messung abgebrochen, da Ausführungsdauer zu lang

{{Klappleiste/Anfang|style=max-width:920px;|style-kopf=text-align:left|style-inhalt=font-size:90%|TITEL=Quellcode für die vier Implementierungen}}
<syntaxhighlight lang="cpp">
#include <cstdint>
#include <bit>        // für std::countr_zero
#include <algorithm>  // für std::swap

using u64 = uint64_t;

// Steinscher Algorithmus
u64 Stein(u64 a, u64 b)
{
    if (b==0) return a;
    if (b&1)
        return a <= b ? Stein(a, b-a) : Stein(b, a-b);
    return a&1 ? Stein(a, b>>1) : Stein(a>>1, b>>1)<<1;
}

// Klassischer Euklidscher Algorithmus mit Subtraktion
u64 Euklid_Sub(u64 a, u64 b)
{
    while (a != b)
        if (a > b) a -= b;  // Wenn a ≫ b oder a ≪ b, dauert diese Ausführung längere Zeit.
        else       b -= a;  // Im schlimmsten Fall (UINT64_MAX, 1) mehrere hundert Jahre.
    return a;
}

// Euklidscher Algorithmus mit Division
u64 Euklid_Div(u64 a, u64 b)
{
    return b ? Euklid_Div(b, a % b) : a;
}

// Hilfsfunktion für Steinscher Algorithmus nach D. E. Knuth (für ab Mitte der 1980er Jahre entwickelte CPU EIN Maschinenbefehl)
unsigned long CountZeros(u64 x)  // liefert für x>0 die Position des niedrigsten gesetzten Bits, für x=0 ist das Verhalten irrelevant
{
//  return std::countr_zero(x);                                   // ab C++20
//  unsigned long ret; ::_BitScanForward64 (& ret, x); return ret;// für Microsoft VS
    return __builtin_ffsll(x) - 1;                                // für GnuC, Clang, ellcc, Intel icc, nvc, zigC++
}

// Steinscher Algorithmus nach D. E. Knuth
u64 Knuth(u64 a, u64 b)
{
    if (a == 0 || b == 0)  // falls eines oder beide Argumente 0 sind,
        return a | b;      // ist das andere Argument oder 0 das Ergebnis

    unsigned long const zeros = CountZeros(a | b);  // LSB-Nullen, werden einmalig bestimmt
    a >>= CountZeros(a);
    do {
        b >>= CountZeros(b);
        if (a > b)
            std::swap (a, b); // vertausche Variablen, damit immer die kleinere von der größeren Zahl abgezogen wird
        b -= a;
    } while (b);
    return a << zeros;
}
</syntaxhighlight>
{{Klappleiste/Ende}}

=== Berechnung mittels Probieren ===
Die einfachste, aber meist langsamste Methode ist das Probieren:
:Beginnend von der kleinsten der Zahlen (daher sollte diese klein sein) wird abwärts zählend die Teilbarkeit geprüft.

<span style="font-size:90%"><math>\operatorname{ggT}(8,\,12)</math></span>
:Teilbar durch 8?&ensp; 8 ist {{0|nich}}''' teilbar''', 12 ist nicht teilbar
:Teilbar durch 7?&ensp; 8 ist nicht teilbar, 12 ist nicht teilbar
:Teilbar durch 6?&ensp; 8 ist nicht teilbar, 12 ist {{0|nich}} '''teilbar'''
:Teilbar durch 5?&ensp; 8 ist nicht teilbar, 12 ist nicht teilbar
:Teilbar durch 4?&ensp; 8 ist {{0|nich}} '''teilbar''', 12 ist {{0|nich}} '''teilbar''' <span style="font-size:90%"><math>\quad\longrightarrow \operatorname{ggT}(8,\,12) = 4</math></span>

<span style="font-size:90%"><math>\operatorname{ggT}(6,\,12)</math></span>
:Teilbar durch 6?&ensp; 6 ist {{0|nich}} '''teilbar''', 12 ist {{0|nich}} '''teilbar''' <span style="font-size:90%"><math>\quad\longrightarrow \operatorname{ggT}(6,\,12) = 6</math></span>

<span style="font-size:90%"><math>\operatorname{ggT}(6,\,93\,099)</math></span>
:Teilbar durch 6?&ensp; 6 ist {{0|nich}} '''teilbar''', 93099 ist nicht teilbar, da ungerade
:Teilbar durch 5?&ensp; 6 ist nicht teilbar, 93099 ist nicht teilbar, da nicht auf 0 oder 5 endend
:Teilbar durch 4?&ensp; 6 ist nicht teilbar, 93099 ist nicht teilbar, da ungerade
:Teilbar durch 3?&ensp; 6 ist {{0|nich}} '''teilbar''', 93099 ist offensichtlich '''teilbar''' <span style="font-size:90%"><math>\quad\longrightarrow \operatorname{ggT}(6,\ 93\,099) = 3</math></span>

=== Berechnung für mehrere Zahlen ===
{{Anker|ggT von mehreren Zahlen}}

==== Berechnung mittels&nbsp;Primfaktorzerlegung ==== <!-- Bitte das &nbsp; stehen lassen! -->
Die Berechnung mittels Primfaktorzerlegung lässt nativ die Berechnung für eine beliebige Menge von Zahlen <math>a_1, \ldots, a_k</math> zu.
Man verwendet alle Primfaktoren, die in jeder der Zahlen vorkommen, mit der jeweils kleinsten vorkommenden Potenz.

Gegeben seien die Primfaktorzerlegungen:
:<math>
\begin{array}{ccccc}
a_1 =  & p_1^{e_{1,1}} & p_2^{e_{1,2}} & \cdots & p_m^{e_{1,m}} \\
a_2 =  & p_1^{e_{2,1}} & p_2^{e_{2,2}} & \cdots & p_m^{e_{2,m}} \\
\vdots\quad & \vdots\;  & \vdots\;         & \ddots & \vdots\;  \\
a_k =  & p_1^{e_{k,1}} & p_2^{e_{k,2}} & \cdots & p_m^{e_{k,m}} \\
\end{array}
</math>

mit <math>e_{i,j} \geq 0</math> dem jeweiligen Exponenten des Primfaktors <math>p_j</math> der Zahl <math>a_i</math> (<math>i = 1, \ldots, k,\;\;j = 1, \ldots, m</math>).

Der ggT berechnet sich zu (mit <math>\min(e_{1,j},\,e_{2,j},\,\ldots, e_{k,j})</math> dem kleinsten Exponenten des Primfaktors <math>p_j</math> aller Zahlen):

:<math>\operatorname{ggT}(a_1, a_2, \ldots, a_k) = \prod_{j=1}^m p_j^{\min(e_{1,j},\,e_{2,j},\,\ldots, e_{k,j})}\ </math>.

;Beispiel:
Gesucht ist der kleinste gemeinsame Teiler von <math>1584,\ 1760</math> und <math>1925</math>.

Die Primfaktorenzerlegung lautet, wobei die jeweils kleinsten Exponenten in Rot, die anderen (irrelevanten) in Grau gesetzt sind:

:<math>1584 = 2^{\color{Gray}4} \cdot 3^{\color{Gray}2} \cdot 5^{\color{Red }0} \cdot 7^{\color{Red }0} \cdot 11^{\color{Red }1}</math>
:<math>1760 = 2^{\color{Gray}5} \cdot 3^{\color{Red }0} \cdot 5^{\color{Gray}1} \cdot 7^{\color{Red }0} \cdot 11^{\color{Red }1}</math>
:<math>1925 = 2^{\color{Red }0} \cdot 3^{\color{Red }0} \cdot 5^{\color{Gray}2} \cdot 7^{\color{Gray}1} \cdot 11^{\color{Red }1}</math>,

die kleinsten Exponenten sind <math>({\color{Red }0},\ {\color{Red }0},\ {\color{Red }0},\ {\color{Red }0},\ {\color{Red }1})</math>. Daher folgt:

:<math>\operatorname{ggT}(1584,\ 1760,\ 1925) = 2^{\color{Red}0} \cdot 3^{\color{Red}0} \cdot 5^{\color{Red}0} \cdot 7^{\color{Red}0} \cdot 11^{\color{Red}1} = 1 \cdot 1 \cdot 1 \cdot 1 \cdot 11 = 11.</math>

;Bemerkung:
Bei Anwendung des jeweils größten Exponenten erhält man (analog) das kleinste gemeinsame Vielfache:
:<math>1584 = 2^{\color{Gray}4} \cdot 3^{\color{Red }2} \cdot 5^{\color{Gray}0} \cdot 7^{\color{Gray}0} \cdot 11^{\color{Red }1}</math>
:<math>1760 = 2^{\color{Red }5} \cdot 3^{\color{Gray}0} \cdot 5^{\color{Gray}1} \cdot 7^{\color{Gray}0} \cdot 11^{\color{Red }1}</math>
:<math>1925 = 2^{\color{Gray}0} \cdot 3^{\color{Gray}0} \cdot 5^{\color{Red }2} \cdot 7^{\color{Red }1} \cdot 11^{\color{Red }1}</math>,

die größten Exponenten sind <math>({\color{Red}5},\ {\color{Red }2},\ {\color{Red }2},\ {\color{Red }1},\ {\color{Red }1})</math>. Daher folgt:
:<math>\operatorname{kgV}(1584,\ 1760,\ 1925) = 2^{\color{Red}5} \cdot 3^{\color{Red}2} \cdot 5^{\color{Red}2} \cdot 7^{\color{Red}1} \cdot 11^{\color{Red}1} = 32 \cdot 9 \cdot 25 \cdot 7 \cdot 11 = 554\,400.</math>

Das Produkt aus <math>\operatorname{ggT}</math> und <math>\operatorname{kgV}</math> ist <math>6\,098\,400</math>, das der drei Zahlen ist <math>5\,366\,592\,000</math>, womit man sieht, dass die Multiplikationsregel für <math>\operatorname{ggT}</math> und <math>\operatorname{kgV}</math> für mehr als zwei Zahlen '''nicht''' gilt.

==== Berechnung mittels Verkettung ====
Wie wir schon festgestellt haben, ist die Berechnung über die Primfaktorenzerlegung nicht die effizienteste Methode.

Die Berechnung des <math>\operatorname{ggT}</math> erfolgt durch Verkettung. Die Reihenfolge (sowohl kommutativ wie assoziativ) ist dabei irrelevant:

:<math>\operatorname{ggT}(a,b,c) = 
       \operatorname{ggT}(\operatorname{ggT}(a,b),c) = 
       \operatorname{ggT}(a,\operatorname{ggT}(b,c))
</math>
:<math>\qquad\qquad\quad = \operatorname{ggT}(b,a,c) = 
       \operatorname{ggT}(b,\operatorname{ggT}(c,a)) = \ldots 
</math>

Für die Berechnung von <math>\operatorname{ggT}(1584,\,1760,\,1925)</math> berechnet man z.&#8239;B. zuerst
:<math>\operatorname{ggT}(1584,\,1760) = 176\qquad </math> und im zweiten Schritt
:<math>\operatorname{ggT}(\ \ 176,\,1925) = \ \ 11</math>.

Der Hintergrund, warum das funktioniert, ist die Eigenschaft des [[Größtes und kleinstes Element|Minimum-Operators]]:
:<math>\min(\mathcal{A} \cup \mathcal{B}) = \min(\min(\mathcal{A}),\,\min(\mathcal{B}))</math>, &emsp;der sich durch das Anwenden auf die Exponenten auf die <math>\operatorname{ggT}</math> durchschlägt:
:<math>\operatorname{ggT}(\mathcal{A} \cup \mathcal{B}) = \operatorname{ggT}(\operatorname{ggT}(\mathcal{A}),\,\operatorname{ggT}(\mathcal{B}))</math>.
<math>\mathcal{A}</math> und <math>\mathcal{B}</math> bezeichnen hier jeweils nichtleere Mengen an ganzen Zahlen, d.&#8239;h. man kann
eine Menge <math>\mathcal{M}</math> in (sinnvollerweise, aber nicht notwendigerweise echte) nichtleere Teilemengen
<math>\emptyset \subset \mathcal{A} \subseteq \mathcal{M}</math> und <math>\emptyset \subset \mathcal{B} \subseteq \mathcal{M}</math> mit <math>\mathcal{A} \cup \mathcal{B} = \mathcal{M}</math> zerlegen und dann die Operation rekursiv anwenden.

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

;Bemerkung:
Das Gleiche gilt für das kleinste gemeinsame Vielfache, nur dass hier das Minimum jeweils durch das Maximum (der Exponenten) ersetzt wird.

=== Berechnen für Polynome ===
Die Bestimmung des <math>\operatorname{ggT}</math> für Polynome läuft auf geschicktes Raten und [[Polynomdivision]]en bzw. auf die [[Satz über rationale Nullstellen|Bestimmung der Nullstellen der Polynome hinaus]].

Letzteres erfolgt folgendermaßen:
:<math>\operatorname{ggT}\left( \sum_{i=0}^k a_i x^i ,\; \sum_{i=0}^m b_i x^i \right) =  

\operatorname{ggT}\left( a_k \prod_{i=0}^k (x - x_{a,i}) ,\; b_m \prod_{i=0}^m (x - x_{b,i}) \right) =

\operatorname{ggT}(a_k,\,b_m)   \prod_{x_i \in \mathcal{M}} \!\!(x - x_i) </math>
wobei <math>\mathcal{M}</math> die Menge aller paarweise identischen Nullstellen der beiden Polynome umfasst.

;Beispiel:
:<math>\operatorname{ggT} (2 x^5 - 28 x^4 + 138 x^3 - 296 x^2 + 280 x - 96,\;6 x^5 - 72 x^4 + 312 x^3 - 612 x^2 + 546 x - 180) = </math>
:<math>\operatorname{ggT} (2(x-1)(x-1)(x-2)(x-4)(x-6),\;6(x-1)(x-1)(x-2)(x-3)(x-5))</math>.

Die gemeinsamen Nullstellen sind die doppelte Nullstelle <math>+1</math> und die einfache Nullstelle <math>+2</math>, weiterhin ist das <math>\operatorname{ggT}(2,\,6) = 2</math>.
:<math>\operatorname{ggT} (2 x^4 - 20 x^3 + 64 x^2 - 76 x + 30,\ 2 x^4 - 16 x^3 + 42 x^2 - 44 x + 16) =  2(x-1)(x-1)(x-2) = 2 x^3 - 8 x^2 + 10 x - 4</math>.

Der rationale Bruch
:<math>\frac{2 x^5 - 28 x^4 + 138 x^3 - 296 x^2 + 280 x - 96}{6 x^5 - 72 x^4 + 312 x^3 - 612 x^2 + 546 x - 180} </math>
lässt sich für <math>x \neq 1,\; 2\ </math> kürzen zu:
:<math>\frac{(x - 6) (x - 4)}{3 (x - 5) (x - 3)} </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> &emsp;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>\begin{array}{lll}
\operatorname{ggT}(e-1,\ e+1)      & = 1 \\
\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}\big(\tfrac{a}{2},\ \tfrac{b}{2}\big) & \text{falls } a \text{ und }        b \text{ gerade} \\
\operatorname{ggT}(a,\ b)          & = \operatorname{ggT}\big(\tfrac{a}{2},\ b\big)     & \text{falls } a \text{ gerade und } b \text{ ungerade} \\
\operatorname{ggT}(a,\ b)          & = \operatorname{ggT}\big(\tfrac{a-b}{2},\ b\big)  & \text{falls } a \text{ und }        b \text{ ungerade} \\
\end{array}
</math>

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

== Anwendungen ==
=== Kürzen von Brüchen ===
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>.&nbsp;Kürzt man mit dem größten gemeinsamen Teiler von Zähler und Nenner, entsteht ein Bruch, der nicht weiter kürzbar ist.<ref>Lutz 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{Red} 6}</math>, also
: <math>\frac{12}{18} = \frac{2 \cdot {\color{Red} 6}}{3 \cdot {\color{Red} 6}} = \frac{2}{3}</math>

{{Anker|gekürzter Bruch}}Ein Bruch mit Zähler <math>a</math> und Nenner <math>b</math>, bei dem <math>\operatorname{ggT}(a,b) = 1</math> 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>, in der Mathematik ''vollständig'' oder ''maximal gekürzter Bruch'' genannt. In der englischsprachigen Literatur wird er „''Simplified fraction''“ oder „''Reduced fraction''“ genannt.

=== Zusammenhang zwischen größtem gemeinsamen Teiler (ggT) und kleinstem gemeinsamen Vielfachen (kgV) ===
;Satz:
:<math>\operatorname{ggT}(a,b) \cdot \operatorname{kgV}(a,b) = a \cdot b</math>

;Beweis: Nachweis für positive ganze Zahlen <math>m</math> und <math>n</math>, 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 ''§ 4. ggT und kgV.''] In: ''math-www.uni-paderborn.de.'' S. 14.</ref>

== Weitere algebraische Strukturen mit ggT ==
Der Begriff des <math>\operatorname{ggT}</math> baut auf dem Begriff der [[Teilbarkeit]] auf, wie er in Ringen definiert ist. Man beschränkt sich bei der Diskussion des <math>\operatorname{ggT}</math> auf [[nullteiler]]freie Ringe, im kommutativen Fall sind das die [[Integritätsring]]e.

Ein Integritätsring, in dem je zwei Elemente einen <math>\operatorname{ggT}</math> besitzen, heißt ''[[ggT-Ring]]'' oder ''ggT-Bereich.'' (In einem <math>\operatorname{ggT}</math>-Ring haben je zwei Elemente auch ein {{nowrap|<math>\operatorname{kgV}</math>.)}}

Im 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 <math>\operatorname{ggT}</math> gegebenenfalls 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 <math>\operatorname{ggT}</math> 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 <math>\operatorname{ggT}</math> sind untereinander assoziiert.

=== Polynomringe ===
Man kann den <math>\operatorname{ggT}</math> 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 <math>\operatorname{ggT}</math>: 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 <math>\operatorname{ggT}</math> von <math>a</math> und <math>b</math>.

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

Ist <math>R</math> ein Integritätsring und haben die Elemente <math>a</math> und <math>b</math> ein <math>\operatorname{kgV}</math>, dann haben sie auch einen <math>\operatorname{ggT}</math>, 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>t</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>t=(m,n)</math> und meint damit dann den ''positiven'' <math>\operatorname{ggT}</math>, geht also von <math>t\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. →&nbsp;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: [https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.zawa/lehre/11elzahl/Skript.pdf ''Elementare Zahlentheorie.'']

== 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.

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

[[Kategorie:Wikipedia.de Artikel]]