Größter Gemeinsamer Teiler

Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle.

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

Das kleinste gemeinsame Vielfache zweier ganzer Zahlen m und n ist die kleinste natürliche Zahl, die sowohl Vielfaches von m als auch Vielfaches von n ist.

Beispiele

Hier werden der Einfachheit halber nur natürliche Zahlen betrachtet.

Größter gemeinsamer Teiler:

12 ist durch die folgenden Zahlen ohne Rest teilbar: 1, 2, 3, 4, 6, 12.
18 hat diese Teiler: 1, 2, 3, 6, 9, 18.
Die gemeinsamen Teiler von 12 und 18 sind also 1, 2, 3, 6 und der größte von diesen ist 6; in Zeichen:

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

Kleinstes gemeinsames Vielfaches:

Die Vielfachen von 12 sind: 12, 24, 36, 48, 60, 72, 84, …
Die Vielfachen von 18 sind: 18, 36, 54, 72, 90, 108, …
Die gemeinsamen Vielfachen von 12 und 18 sind also 36, 72, 108, … und das kleinste von diesen ist 36; in Zeichen:

$\operatorname{kgV}(12, 18) = 36$ .

Anwendungen in der Bruchrechnung

Kürzen:

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

Hauptnenner:

Angenommen, wir möchten die Brüche $\tfrac{17}{21}$ und $\tfrac{44}{35}$ addieren. Dazu müssen diese durch Erweitern auf einen gemeinsamen Nenner gebracht werden. Man könnte natürlich einfach 21 mit 35 multiplizieren, was 735 ergibt. Der kleinstmögliche gemeinsame Nenner (der sog. Hauptnenner) ist aber $\operatorname{kgV}(21,35) = 105$. Die beiden Brüche werden auf diesen Nenner erweitert und dann addiert:

$\frac{17}{21} + \frac{44}{35} = \frac{5 \cdot 17}{5 \cdot 21} + \frac{3 \cdot 44}{3 \cdot 35} = \frac{85 + 132}{105} = \frac{217}{105}$

Berechnung

Berechnung über die Primfaktorzerlegung

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

$3528 = 2^{\color{Red}3} \cdot 3^{\color{Red}2} \cdot 7^{\color{Red}2}$

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

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

$\operatorname{ggT}(3528,3780) = 2^{\color{OliveGreen}2} \cdot 3^{\color{Red}2} \cdot 7^{\color{OliveGreen}1} = 252$

Für das kgV nimmt man die Primfaktoren, die in mindestens einer der beiden Zerlegungen vorkommen, und als zugehörigen Exponenten den jeweils größeren der Ausgangsexponenten:

$\operatorname{kgV}(3528,3780) = 2^{\color{Red}3} \cdot 3^{\color{OliveGreen}3} \cdot 5^{\color{OliveGreen}1} \cdot 7^{\color{Red}2} = 52920$

Euklidischer und steinscher Algorithmus

Die Berechnung der Primfaktorzerlegung großer Zahlen und damit auch die Bestimmung des größten gemeinsamen Teilers nach obiger Methode ist sehr aufwändig. Mit dem euklidischen Algorithmus existiert jedoch ein effizientes Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen. Dieses Verfahren wird durch den steinschen Algorithmus noch weiter verbessert.

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

$\begin{align} 1071 &: 1029 &= \ &1 &\ \operatorname{Rest} &\ 42\\ 1029 &: 42 &= \ &24 &\ \operatorname{Rest} &\ 21\\ 42 &: 21 &= \ &2 &\ \operatorname{Rest} &\ 0 \end{align}$

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

Zusammenhang von ggT und kgV

Es gilt die folgende Formel (wobei der Fall m = n = 0 ausgeschlossen ist):

$\operatorname{kgV}(m,n) = \frac{|m \cdot n|}{\operatorname{ggT}(m,n)}$

Damit lässt sich das kgV berechnen, falls der ggT (z. B. mit dem euklidischen Algorithmus) bereits bestimmt wurde. Umgekehrt kann man mit dieser Formel auch den ggT aus dem kgV berechnen.

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.

Rechenregeln für den ggT

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

• $\operatorname{ggT}(a, b) = \operatorname{ggT}(b, a)$ (Kommutativgesetz)
• $\operatorname{ggT}(-a, 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}(b,a \;\bmod\; b)$ (b > 0)
• $\operatorname{ggT}(a, b) = \operatorname{ggT}(b,a-b)$
• $\operatorname{ggT}(m a, m b) = m \cdot\operatorname{ggT}(a, b)$ (Distributivgesetz)
• $\operatorname{ggT}(a + m b, b) = \operatorname{ggT}(a, b)$

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

• $\operatorname{ggT}(a : m, b : m) = \operatorname{ggT}(a, b) : m$

Ist $a \equiv b\ \bmod\ m$ (a und b sind kongruent modulo m), dann gilt:

• $\operatorname{ggT}(a, m) = \operatorname{ggT}(b, m)$

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

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

Berechnung des ggT und des kgV von mehreren Zahlen

Der $\operatorname{ggT}$ und das $\operatorname{kgV}$ lassen sich von beliebig vielen Zahlen berechnen, da beide Abbildungen assoziativ sind:

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

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

GgT und kgV in weiteren algebraischen Strukturen

$\operatorname{kgV}$ und $\operatorname{ggT}$ lassen sich nicht nur für natürliche (und ganze) Zahlen definieren. Man kann sie z. B. auch für Polynome bilden. Statt der Primzahlzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren:

f(x) = x² + 2xy + y² = (x + y)²

g(x) = x² − y² = (x + y)(x − y)

Dann ist $\operatorname{ggT}(f, g) = x + y$ und $\operatorname{kgV}(f, g) = (x + y)^2 (x - y)$.

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

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

Ist d ein Ringelement, das sowohl Teiler von a als auch Teiler von b ist, dann heißt d ein gemeinsamer Teiler von a und b. Gilt zusätzlich, dass jeder weitere gemeinsame Teiler von a und b auch ein Teiler von d ist, dann heißt d ein größter gemeinsamer Teiler von a und b.

Analog ist das $\operatorname{kgV}$ definiert: Ein Ringelement v heißt kleinstes gemeinsames Vielfaches zweier Ringelemente a und b, wenn v ein gemeinsames Vielfaches von a und b ist und seinerseits jedes andere gemeinsame Vielfache von a und b ein Vielfaches von v ist.

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

$d = \operatorname{ggT}(a, b)\quad:\Longleftrightarrow\quad d \mid a,\; d \mid b,\; \forall e \in R: (e \mid a,\, e \mid b) \Rightarrow e \mid d$

$v = \operatorname{kgV}(a, b)\quad:\Longleftrightarrow\quad a \mid v,\; b \mid v,\; \forall e \in R: (a \mid e,\, b \mid e) \Rightarrow v \mid e$

Diese allgemeinere Definition lässt sich auf mehrere Zahlen ausweiten (sogar auf unendlich viele).

Beispiel: Im gaußschen Zahlenring $\Z+\mathrm{i}\Z$ ist der größte gemeinsame Teiler von 2 und 1 + 3i gerade 1 + i, denn 2 = − i(1 + i)² und 1 + 3i = (1 + i)(2 + i). Genau genommen ist 1 + i ein größter gemeinsamer Teiler, da alle zu dieser Zahl assoziierten Zahlen ebenfalls größte gemeinsame Teiler sind.

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

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

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

Beispiel

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 „$\operatorname{ggT}$-$\operatorname{kgV}$-Gleichung“, dass v assoziiert zu $k:=(1 + \sqrt{-3})\cdot2$ 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}$.

Ein Integritätsring, in dem je zwei Elemente einen $\operatorname{ggT}$ besitzen, heißt $\operatorname{ggT}$-Ring oder $\operatorname{ggT}$-Bereich.

In einem $\operatorname{ggT}$-Ring haben je zwei Elemente auch ein $\operatorname{kgV}$.

In einem faktoriellen Ring haben je zwei Elemente einen $\operatorname{ggT}$.

In einem euklidischen Ring lässt sich der $\operatorname{ggT}$ zweier Elemente mit dem euklidischen Algorithmus bestimmen.

Alternative Notationen

Die englischen Bezeichnungen gcd (greatest common divisor) für ggT und lcm (least common multiple) für kgV sind in mathematischen Texten ebenfalls verbreitet.

Oft wird auch $(m,\, n)$ als Kurzschreibweise für $\operatorname{ggT}(m, n)$ verwendet.

Weblinks

• Online-Tool zur Berechnung des ggT und des kgV von zwei oder drei Zahlen
• Verschiedene Online-Tools zur Primfaktorzerlegung, ggT und kgV.
• Online-Tool zur Berechnung des ggT zweier Zahlen