Formelsammlung Mathe

Größter gemeinsamer Teiler (ggT)

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:

ggT von 12 und 15

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

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:

FormelBedeutung
Kommutativgesetzt für den ggTKommutativgesetz
Distributivgesetz für den ggTDistributivgesetz
Assoziativgesetz für den ggTAssoziativgesetz
Vorzeichen im ggTVorzeichen haben keinen Einfluss auf den ggT
ggT einer Zahl mit NullDer größte gemeinsame Teiler einer Zahl mit Null ist der Betrag der Zahl selbst
ggT einer Zahl mit EinsDer größte gemeinsame Teiler einer Zahl mit Eins ist die Eins selbst
Addition mit ggTAddition 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:

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:

Primfaktorzerlegung von 17.640

Und danach die Primfaktorzerlegung von 4.158

Primfaktorzerlegung 4158

Die Primfaktoren, die in beiden Primfaktorzerlegungen vorkommen sind: 2, 3 und 7. Das Produkt der gemeinsamen Primfaktoren in jeweils der kleineren Potenz ist:

ggT von 17640 und 4158

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:

So können wir beispielsweise mit dem euklidischen Algorithmus den größten gemeinsamen Teiler von: 10.893 und 24.531 ausrechnen:

Beispiel zum Euklidischen Algorithmus

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.