Als größten gemeinsamen Teiler von zwei Zahlen a und b, bezeichnet man die größte Zahl m, die sowohl a als auch b ohne Rest teilt. Beispielsweise ist der größte gemeinsame Teiler von 15 und 12 die Zahl 3. Die Zahl 3 ist nämlich die größte Zahl, die sowohl 12 (12/3 = 4), als auch 15 (15/3 = 5) ohne Rest teilt. Für den größten gemeinsamen Teiler ist die Abkürzung ggT üblich. Sie wird in vielen mathematischen Texte benutzt. Oft wird sie auch als Funktion notiert:
Um sich die Bedeutung des Begriffs größter gemeinsamer Teiler zu verdeutlichen, sollte man sich die Konsequenz verdeutlichen, die jeder einzelne seiner Bestandteile hat. Wir beginnen am besten beim letzten und arbeiten uns nach vorne
- Teiler: Ein Teiler ist jede Zahl, die eine andere Zahl ohne Rest teilt. Beispielsweise hat 15 die Teiler 1, 3, 5 und 15. Die Zahl 24 hat die Teiler 1, 2, 3, 4, 6, 8, 12 und 24. Ein Primzahl hat nur zwei Teiler 1 und die Zahl selbst.
- gemeinsamer Teiler: Da es sich beim ggT um einen gemeinsamen Teiler handelt, ist klar, dass er immer nur als Eigenschaft von zwei Zahlen zu betrachten ist. Es wäre sinnlos vom ggT einer einzelnen Zahl zu sprechen. Gemeinsam bedeutet, dass nur Teiler betrachtet werden, die beide Zahlen ohne Rest teilen. Genaugenommen handelt es sich bei den gemeinsamen Teilern um die Schnittmenge der Mengen aller Teiler beider Zahlen. Beispielsweise hat die Zahl 30 die Teiler 1, 2, 3, 5, 6, 10, 15 und 30. Die Zahl 12 hat die Teiler 1, 2, 3, 4, 6 und 12. Gemeinsame Teiler beider Zahlen sind: 1, 2, 3 und 6. Die Zahl 12 ist nur Teiler von sich selbst, aber kein Teiler von 30. Die Zahlen 10, 15 und 30 sind nur Teiler von 30 aber keine Teiler von 12.
- größter gemeinsamer Teiler: Nachdem wir festgestellt haben, dass eine Zahl mehrere Teiler und zwei Zahlen mehrere gemeinsame Teiler haben können, legen wir jetzt fest, dass uns nur der größte unter ihnen interessiert. Im Bereich der ganzen Zahlen ist damit ein ggT eindeutig festgelegt. Man kann also nicht nur sagen, dass 6 ein größter gemeinsamer Teiler von 30 und 12 ist, sondern man muss sogar sagen, 6 sei der größte gemeinsame Teiler von 30 und 12. Diese Eindeutigkeit des ggT wird durch das Attribut größter festgelegt.
Für Schüler ist der größte gemeinsame Teiler besonders in der Bruchrechnung wichtig. Beim Kürzen von Brüchen ist es von Vorteil, den größten gemeinsamen Teiler von Zähler und Nenner zu kennen. Kürzt man den Bruch nämlich mit dem ggT ist er vollständig gekürzt. Zählen und Nenner haben dann keinen weiteren gemeinsamen Teiler mehr, durch den sie sich noch kürzen ließen. Hieran wird auch noch eine andere Eigenschaft des ggT deutlich: Alle gemeinsamen Teiler zweier Zahlen sind Teiler des ggT.
Rechenregeln für den ggT
Für den größten gemeinsamen Teiler gelten folgende Rechenregel:
| Formel | Bedeutung |
|---|---|
 |
Kommutativgesetz |
 |
Distributivgesetz |
 |
Assoziativgesetz |
 |
Vorzeichen haben keinen Einfluss auf den ggT |
 |
Der größte gemeinsame Teiler einer Zahl mit Null ist der Betrag der Zahl selbst |
 |
Der größte gemeinsame Teiler einer Zahl mit Eins ist die Eins selbst |
 |
Addition des Vielfachen der einen Zahl zur anderen ändert den ggT nicht |
Den größten gemeinsamen Teiler ausrechen
Den größten gemeinsamen Teiler zweier Zahlen kann man natürlich wie oben vorgeführt direkt bestimmen, indem man die Teilermengen beider Zahlen bildet, anschließend alle Zahlen wegstreicht, die nur eine der beiden Zahlen teilen, und unter den verbliebenen Zahlen die größte herraussucht.
Die vorgehen ist für kleinere Zahlen bis 50 – in Ausnahmefällen bis 100 – praktikabel. Für größere Zahlen wird es aber schnell unhandlich. Was ist beispielsweise der größte gemeinsame Teiler von 17.640 und 4.158?
Hier hilft uns die Methode der Primfaktorzerlegung weiter. Sie umfasst diese Schritte:
- Bilde für beide Zahlen die Primfaktorzerlegung
- Ermittle für alle Primfaktoren, die in beiden Primfaktorzerlegung vorkommen, die jeweils kleinere Potenz.
- Bilde das Produkt der gemeinsamen Primfaktoren mit der jeweils kleineren Potenz
Dies Vorgehen klingt erst einmal kompliziert wird aber an einem Beispiel gut verständlich. Wie bestimmen hierfür den größten gemeinsam Teiler von 17.640 und 4.158. Zuerst bilden wir die Primfaktorzerlegung von 17.640:
Und danach die Primfaktorzerlegung von 4.158
Die Primfaktoren, die in beiden Primfaktorzerlegungen vorkommen sind: 2, 3 und 7. Das Produkt der gemeinsamen Primfaktoren in jeweils der kleineren Potenz ist:
Dies ist der gesuchte größte gemeinsame Teiler.
Euklidischer Algorithmus
Die Berechnung des größten gemeinsamen Teilers über die Primfaktorzerlegung ist zwar schon etwas handlicher, aber immer noch sehr aufwändig. Gerade bei größeren Zahlen ist es ein nicht unerheblicher Aufwand eine Primfaktorzerlegung zu finden. Eine effizienztere Methode, den größten gemeinsamen Teiler zu finden, ist der Euklidische Algorithmus.
Der Euklidische Algorithmus ist ein sogenannter rekursiver Algorithmus. Das bedeutet, dass derselbe Rechenschritt mehrmals wiederholt wird, wobei sich die Zahlen, mit denen gerechnet wird, aus dem Ergebnis des letzten Rechenschritts ergeben.
Der Euklidische Algorithmus lautet:
- Nimm zwei Zahlen a und b, so dass a > b ist.
- Dividiere a / b mit Rest
- Wenn der Rest 0 ist, bist du fertig. Der größte gemeinsame Teiler ist dann genau b.
- Wenn der Rest größer als 0 ist, wiederhole die Rechnung für b und den Rest.
So können wir beispielsweise mit dem euklidischen Algorithmus den größten gemeinsamen Teiler von: 10.893 und 24.531 ausrechnen:
Der größte gemeinsame Teiler der beiden Zahlen ist also 3. Dies konnten wir mit dem Euklidischen Algorithmus sehr leicht berechnen. Dank der einfachen Rechenvorschrift, können wir die notwendigen Schritte solange mechanisch abarbeiten, bis wir das Ergebnis haben.