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

Der ${\displaystyle \operatorname {ggT} }$ ist die größte natürliche Zahl, durch die sich zwei ganze Zahlen ohne Rest teilen lassen. Der ${\displaystyle \operatorname {ggT} }$ zweier ganzer Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ ist eine ganze Zahl ${\displaystyle m}$ mit der Eigenschaft, dass sie Teiler sowohl von ${\displaystyle a}$ als auch von ${\displaystyle b}$ ist und dass jede ganze Zahl, die ebenfalls die Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ teilt, auch Teiler von ${\displaystyle m}$ ist. Beim Ring ${\displaystyle \mathbb {Z} }$ der ganzen Zahlen (der eine Totalordnung > besitzt) normiert man den ${\displaystyle \operatorname {ggT} }$ auf die größte ganze solche Zahl ${\displaystyle |m|}$.

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

Die englische Bezeichnung gcd (greatest common divisor) für ${\displaystyle \operatorname {ggT} }$ ist in mathematischen Texten ebenfalls verbreitet.

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

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

Berechnung

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);
}

int GreatestCommonDivisor(int a, int b) {
  if (a == 0)
    return b;
  if (b == 0)
    return a;
  if (a < b)
    return GreatestCommonDivisor(b, a);
  return GreatestCommonDivisor(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:

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

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

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

also:

${\displaystyle \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 ${\displaystyle \operatorname {ggT} (144,160)=16}$ berechnen und danach ${\displaystyle \operatorname {ggT} (16,175)=1,}$ denn als eine zweistellige Verknüpfung auf den natürlichen Zahlen ist der ${\displaystyle \operatorname {ggT} }$ assoziativ:

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

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

Rechenregeln

Für ganze Zahlen ${\displaystyle a,b,c}$ gilt – mit ${\displaystyle |a|}$ als dem Betrag von ${\displaystyle a}$:

	●	${\displaystyle \operatorname {ggT} (a,b)}$	${\displaystyle =\operatorname {ggT} (b,a)}$	(Kommutativgesetz)
	●	${\displaystyle \operatorname {ggT} (\pm a,\pm b)}$	${\displaystyle =\operatorname {ggT} (a,b)}$
	●	${\displaystyle \operatorname {ggT} (a,a)}$	${\displaystyle =|a|}$
	●	${\displaystyle \operatorname {ggT} (a,0)}$	${\displaystyle =|a|}$
	●	${\displaystyle \operatorname {ggT} (a,1)}$	${\displaystyle =1}$
	●	${\displaystyle \operatorname {ggT} (a,b\;{\bmod {\;}}a)}$	${\displaystyle =\operatorname {ggT} (a,b)}$	${\displaystyle (a\neq 0)}$
	●	${\displaystyle \operatorname {ggT} (a,b+ac)}$	${\displaystyle =\operatorname {ggT} (a,b)}$
	●	${\displaystyle \operatorname {ggT} (a,b,c)}$	${\displaystyle =\operatorname {ggT} (a,\,\operatorname {ggT} (b,c))=\operatorname {ggT} (\operatorname {ggT} (a,b),\,c)}$	(Assoziativgesetz)
	●	${\displaystyle \operatorname {ggT} (a\cdot c,b\cdot c)}$	${\displaystyle =\operatorname {ggT} (a,b)\cdot |c|}$	(Distributivgesetz)
	●	Ist ${\displaystyle c}$ ein gemeinsamer Teiler von ${\displaystyle a}$ und ${\displaystyle b}$, dann gilt: ${\displaystyle c}$   teilt   ${\displaystyle \operatorname {ggT} (a,b)}$   und     ${\displaystyle \operatorname {ggT} (a:c,b:c)\,=\operatorname {ggT} (a,b):|c|}$		für   ${\displaystyle c\neq 0.}$
	●	Ist ${\displaystyle a\equiv b\ {\bmod {\ }}c}$   (${\displaystyle a}$ und ${\displaystyle b}$ sind kongruent modulo ${\displaystyle c}$), dann gilt:     ${\displaystyle \operatorname {ggT} (a,c)\qquad \;\;\,=\operatorname {ggT} (b,c)}$

Aus der genannten Rechenregel ${\displaystyle \operatorname {ggT} (a,0)=|a|}$ ergibt sich speziell ${\displaystyle \operatorname {ggT} (0,0)=0}$. Dies ergibt sich auch daraus, dass jede ganze Zahl ${\displaystyle a}$ (sogar die 0 selbst) wegen ${\displaystyle 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 ${\displaystyle \operatorname {ggT} }$ eine multiplikative Funktion, denn für teilerfremde Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ gilt:

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

Lemma von Bézout

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

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

Beispielsweise besitzt der größte gemeinsame Teiler von ${\displaystyle 12}$ und ${\displaystyle 18}$ die folgende Darstellung:

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

Die Koeffizienten ${\displaystyle s}$ und ${\displaystyle t}$ können mit dem erweiterten euklidischen Algorithmus berechnet werden.

Sonderfälle

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

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

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

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

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

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

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

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

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

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

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

Anwendungen

Weitere algebraische Strukturen mit ggT

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

Ein Integritätsring, in dem je zwei Elemente einen ${\displaystyle \operatorname {ggT} }$ besitzen, heißt ggT-Ring oder ggT-Bereich. (In einem ${\displaystyle 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 ${\displaystyle \operatorname {ggT} }$ gegebenenfalls nicht mehr eindeutig als nicht-negativ normieren, sondern nur bis auf Assoziiertheit bestimmen. Zwei Elemente ${\displaystyle a}$ und ${\displaystyle b}$ sind assoziiert, in Zeichen ${\displaystyle a\sim b}$, wenn es eine Einheit ${\displaystyle \epsilon }$ mit ${\displaystyle a=b\cdot \epsilon }$ gibt.

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

${\displaystyle 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 ${\displaystyle d}$ sind genau die Elemente aus ${\displaystyle R}$, die alle Elemente aus ${\displaystyle M}$ teilen. Die ${\displaystyle \operatorname {ggT} }$ sind untereinander assoziiert.

Analytische Zahlentheorie

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

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

Einzelnachweise

1. ↑ Schüler-Duden: Die Mathematik I. Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 167.
2. ↑ Calvin T. Long: Elementary Introduction to Number Theory. D. C. Heath and Company, Boston, 1972, ISBN 978-0-669-62703-9, S. 33.
3. ↑ Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8, S. 15.
4. ↑ Schüler-Duden: Die Mathematik I. Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 354.
5. ↑ Lambacher Schweizer: Mathematik für Gymnasien 5 Niedersachsen. Klett Verlag, Stuttgart 2006, ISBN 978-3-12-734551-3, S. 197.
6. ↑ Schüler-Duden: Die Mathematik I. Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 100
7. ↑ Schüler-Duden: Die Mathematik I. Dudenverlag Mannheim, 1990, ISBN 3-411-04205-2, S. 168.
8. ↑ Harald Scheid: Einführung in die Zahlentheorie. Klett Verlag, Stuttgart, 1972, ISBN 3-12-983240-8, S. 78.
9. ↑ Lemma von Bézout.
10. ↑ L. Engelmann (Hrsg.): Kleiner Leitfaden Mathematik. Paetec, Berlin 1997, ISBN 3-89517-150-6, S. 51/2.
11. ↑ Schüler-Duden: Die Mathematik I. Dudenverlag, Mannheim. Leipzig, Wien, Zürich 1990, ISBN 3-411-04205-2, S. 48.
12. ↑ § 4. ggT und kgV. In: math-www.uni-paderborn.de. S. 14.

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

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