Der größte gemeinsame Teiler mehrerer ganzer Zahlen ist die größte positive Zahl, die jede davon ohne Rest teilt. Die Abkürzung lautet ggT. Er kürzt Brüche und Verhältnisse, teilt Mengen in gleich große Gruppen und bestimmt die größte Länge, die in mehrere Maße genau hineinpasst.
Gemeinsame Teiler machen die Definition sichtbar
Die positiven Teiler von 18 sind 1, 2, 3, 6, 9 und 18. Für 24 lauten sie 1, 2, 3, 4, 6, 8, 12 und 24. Gemeinsam sind 1, 2, 3 und 6; daher ist der ggT 6. Bei großen Zahlen wird das vollständige Auflisten unpraktisch.
Wähle unten zwei positive ganze Zahlen. Der euklidische Algorithmus zeigt jede Division und jeden Rest, sodass der Weg nachvollziehbar bleibt.
Verfolge den euklidischen Algorithmus
Jede Zeile ersetzt das vorige Paar durch Divisor und Rest; der letzte Rest ungleich null ist der ggT.
Primfaktoren behalten die kleinsten gemeinsamen Exponenten
Zerlege jede Zahl in Primfaktoren. Für jeden überall vorkommenden Primfaktor wird der kleinste Exponent gewählt. Das Produkt dieser Potenzen ist der ggT und funktioniert auch für mehr als zwei Zahlen.
Bei 84 und 126 sind je ein Faktor 2, 3 und 7 gemeinsam. Ihr Produkt ist 42. Die Kontrolle lautet 84 geteilt durch 42 gleich 2 und 126 geteilt durch 42 gleich 3. Eine zusätzliche Primzahlpotenz fehlt mindestens in einer Zerlegung.
Der euklidische Algorithmus skaliert besser
Für (a>b>0) teile (a) durch (b). Ersetze das Paar durch (b) und den Rest und wiederhole. Gemeinsame Teiler bleiben erhalten, weil jeder Teiler von (a) und (b) auch (a-qb) teilt. Beim Rest null ist der letzte Rest ungleich null der ggT.
Für 252 und 105 folgen die Reste 42 und 21, dann null. Der ggT ist 21, ohne beide Zahlen vollständig zu faktorisieren. Üblicherweise gilt (gcd(a,0)=|a|); (0,0) bleibt meist undefiniert.
Identitäten liefern unabhängige Prüfungen
Vertauschen der Eingaben ändert den ggT nicht, und das Ergebnis wird positiv genommen. Nach Division beider Zahlen durch den ggT sind die Quotienten teilerfremd. Außerdem ist ggT mal kleinstes gemeinsames Vielfaches gleich dem Betrag des Zahlenprodukts.
Exakte Aufteilung in der Praxis
Ein Boden von 252 cm mal 105 cm soll ohne Zuschnitt mit möglichst großen quadratischen Fliesen bedeckt werden. Die Seitenlänge muss beide Maße teilen und beträgt 21 cm. Es passen 12 mal 5, insgesamt also 60 Fliesen.
Der ggT beantwortet nur Aufgaben mit exakter Teilbarkeit. Sind Verschnitt, Messtoleranzen oder gerundete Längen erlaubt, benötigt die praktische Entscheidung ein anderes Modell. Wandle alle Maße vorher in dieselbe exakte Einheit um.
Für drei oder mehr Zahlen wird schrittweise gerechnet: zuerst der ggT zweier Zahlen, dann der ggT dieses Ergebnisses mit der nächsten. Aus 48 und 72 entsteht 24; zusammen mit 60 ergibt sich 12. Negative Vorzeichen ändern die Teilbarkeit nicht, deshalb werden Beträge verwendet und der ggT positiv angegeben. Ist der gefundene Wert größer als der Betrag einer Eingabe ungleich null, liegt sicher ein Fehler vor. Eine Probe durch Division sollte überall ganzzahlige Quotienten liefern.
