Größter gemeinsamer Teiler
In diesem Kapitel schauen wir uns an, was der größte gemeinsame Teiler ist.
Erforderliches Vorwissen
Einordnung
Wenn wir die Teilermengen von $12$ und $18$ auf Gemeinsamkeiten untersuchen,
$$ T_{12} = \{{\color{green}1}, {\color{green}2}, {\color{green}3}, 4, {\color{green}6}, 12\} $$
$$ T_{18} = \{{\color{green}1}, {\color{green}2}, {\color{green}3}, {\color{green}6}, 9, 18\} $$
dann stellen wir fest, dass die Teiler ${\color{green}1}$, ${\color{green}2}$, ${\color{green}3}$ und ${\color{green}6}$ in beiden Mengen vorkommen. Unter den gemeinsamen Teilern spielt der größte gemeinsame Teiler (hier: die ${\color{green}6}$) eine besondere Rolle.
Definition
Der größte gemeinsame Teiler mehrerer natürlicher Zahlen ist die größte Zahl, die Teiler aller dieser Zahlen ist.
Schreibweise
$\text{ggT}(a, b)$
Sprechweise
g g T von a und b
Der größte gemeinsame Teiler von a und b
Größten gemeinsamen Teiler berechnen
Es gibt verschiedene Rechenverfahren, um den größten gemeinsamen Teiler zu berechnen.
ggT über Teilermengen
Berechne den größten gemeinsamen Teiler von $12$ und $18$.
Teilermengen bestimmen
$$ T_{12} = \{1, 2, 3, 4, 6, 12\} $$
$$ T_{18} = \{1, 2, 3, 6, 9, 18\} $$
Gemeinsame Teiler markieren
$$ T_{12} = \{\underline{1}, \underline{2}, \underline{3}, 4, \underline{6}, 12\} $$
$$ T_{18} = \{\underline{1}, \underline{2}, \underline{3}, \underline{6}, 9, 18\} $$
Größten gemeinsamen Teiler markieren
$$ T_{12} = \{\underline{1}, \underline{2}, \underline{3}, 4, {\color{green}\underline{6}}, 12\} $$
$$ T_{18} = \{\underline{1}, \underline{2}, \underline{3}, {\color{green}\underline{6}}, 9, 18\} $$
Ergebnis aufschreiben
$$ \text{ggT}(12, 18) = 6 $$
Anmerkung
Die Teilermengen mehrerer Zahlen zu bestimmen, kann ziemlich zeitaufwändig sein. Wenn du die Primfaktorzerlegung bereits beherrscht, ist das folgende Verfahren einfacher.
ggT über Primfaktorzerlegung
Der ggT zweier natürlicher Zahlen ist das Produkt ihrer gemeinsamen Primfaktoren.
Berechne den größten gemeinsamen Teiler von $12$ und $18$.
Primfaktorzerlegung durchführen
$$ 12 = 2 \cdot 2 \cdot 3 $$
$$ 18 = 2 \cdot 3 \cdot 3 $$
Gemeinsame Primfaktoren markieren
$$ 12 = \underline{2} \cdot 2 \cdot \underline{3} $$
$$ 18 = \underline{2} \cdot \underline{3} \cdot 3 $$
Gemeinsame Primfaktoren miteinander multiplizieren
$$ \text{ggT}(12, 18) = 2 \cdot 3 = 6 $$
Anmerkung
Wenn der größte gemeinsame Teiler von sehr großen Zahlen berechnet werden soll, kann auch dieses Verfahren ziemlich zeitaufwändig sein. Zum Glück hat ein griechischer Mathematiker namens Euklid bereits vor über 2000 Jahren eine Lösung für dieses Problem gefunden.
ggT über euklidischen Algorithmus
Berechne den größten gemeinsamen Teiler von $12$ und $18$.
Größere durch kleinere Zahl dividieren
$$ 18 : 12 = 1 \text{ Rest } 6 $$
Divisor durch Rest dividieren
Diesen Schritt führen wir solange durch, bis die Rechnung aufgeht.
Der letzte Divisor ist dann der ggT der beiden Ausgangszahlen.
$$ 12 : {\color{green}6} = 2 $$
Ergebnis aufschreiben
$$ \text{ggT}(18, 12) = {\color{green}6} $$
Berechne den größten gemeinsamen Teiler von $144$ und $256$.
Größere durch kleinere Zahl dividieren
$$ 256 : 144 = 1 \text{ Rest } 112 $$
Divisor durch Rest dividieren
Diesen Schritt führen wir solange durch, bis die Rechnung aufgeht.
Der letzte Divisor ist dann der ggT der beiden Ausgangszahlen.
$$ 144 : 112 = 1 \text{ Rest } 32 $$
$$ 112 : 32 = 3 \text{ Rest } 16 $$
$$ 32 : {\color{green}16} = 2 $$
Ergebnis aufschreiben
$$ \text{ggT}(144, 256) = {\color{green}16} $$
Anmerkung
Im Gegensatz zu den beiden erstgenannten Verfahren kann mit dem euklidischen Algorithmus lediglich der ggT zweier Zahlen, also nicht der ggT mehrerer Zahlen, berechnet werden.
ggT über kgV
Zwischen dem kleinsten gemeinsamen Vielfachen und dem ggT gilt folgender Zusammenhang:
$$ \text{ggT}(a, b) \cdot \text{kgV}(a, b) = a \cdot b $$
Daraus folgt: $\text{ggT}(a, b) = \frac{a \cdot b}{\text{kgV}(a, b)}$
Berechne den größten gemeinsamen Teiler von $144$ und $256$.
kgV berechnen
$$ \text{kgV}(144, 256) = 2304 $$
Zwischenergebnis in die Formel einsetzen und ausrechnen
$$ \begin{align*} \text{ggT}(144, 256) &= \frac{a \cdot b}{\text{kgV}(a, b)} \\[5px] &= \frac{144 \cdot 256}{2304} \\[5px] &= \frac{36864}{2304} \\[5px] &= 16 \end{align*} $$
Anmerkung
Da die Berechnung des kgV in der Regel zeitaufwändiger ist als die des ggT, wird die obige Formel eigentlich nur dann eingesetzt, wenn das kleinste gemeinsame Vielfache gesucht ist.
Praktische Bedeutung
Online-Rechner
Größten gemeinsamen Teiler online berechnen
Ausblick
Gilt $\text{ggT}(a, b) = 1$, so heißen $a$ und $b$ teilerfremd, da in diesem Fall $a$ und $b$ außer der $1$, die bekanntlich Teiler jeder natürlichen Zahl ist, keine weiteren gemeinsamen Teiler besitzen.
