Der größte gemeinsame Teiler (ggT)

Zuletzt bearbeitet am 26.03.2018 um 21:38 Uhr.

Brüche lassen sich in vielen verschiedenen "Versionen" darstellen, so ist \(\frac{3}{8}=\frac{6}{16}=\frac{9}{24}\). Um Missverständnisse zu vermeiden und eine einheitliche Schreibweise zu definieren, gibt man Brüche immer mit den kleinsten möglichen natürlichen Zahlen an (in dem Beispiel wäre es \(\frac{3}{8}\)). Schnell zu diesem gekürzten Bruch zu kommen ist eine der Anwendungen des größten gemeinsamen Teilers (ggT). Und wie man diesen bildet, findest du hier: Dazu gibt es mehrere Möglichkeiten, die ich dir alle hier vorstellen möchte.

Primfaktorzerlegung

Wie schon zur Bestimmung des kgV braucht man zur Bestimmung des ggT die Primfaktorzerlegung. Deshalb ist der erste Schritt, die Zerlegung der beiden Zahlen (als Beispiel 84 und 266) in ihre Primfaktoren:

Ist 84 durch 2 ohne Rest teilbar? Ja

$$84:2=42$$

Ist 42 durch 2 ohne Rest teilbar? Ja

$$42:2=21$$

Ist 21 durch 2 ohne Rest teilbar? Nein

Ist 21 durch 3 ohne Rest teilbar? Ja

$$21:3=7$$

Ist 7 durch 3 ohne Rest teilbar? Nein

Ist 7 durch 5 ohne Rest teilbar? Nein

Ist 7 durch 7 ohne Rest teilbar? Ja

$$7:7=1$$

Die Primfaktoren von 84 sind also: \(84=2^2·3^1·7^1\). Und nun wird noch die zweite Zahl (266) in die Primfaktoren zerlegt:

Ist 266 durch 2 ohne Rest teilbar? Ja

$$266:2=133$$

Ist 133 durch 2 ohne Rest teilbar? Nein

Ist 133 durch 3 ohne Rest teilbar? Nein

Ist 133 durch 5 ohne Rest teilbar? Nein

Ist 133 durch 7 ohne Rest teilbar? Ja

$$133:7=19$$

Ist 19 durch 7 ohne Rest teilbar? Nein

Ist 19 durch 11 ohne Rest teilbar? Nein

Ist 19 durch 13 ohne Rest teilbar? Nein

Ist 19 durch 17 ohne Rest teilbar? Nein

Ist 19 durch 19 ohne Rest teilbar? Ja

$$19:19=1$$

Die Primfaktoren von 266 sind also: \(266=2^1·7^1·19^1\). Jetzt, wo wir die beiden Primfaktoren kennen, geht's weiter mit dem nächsten Schritt. Um den ggT der beiden Zahlen zu finden muss man jetzt nur noch alle Primfaktoren, die beiden Zahlen vorkommen multiplizieren und jeweils den kleineren Exponenten beibehalten:

$$ggT(84, 266)=2^1·7^1=14$$

Wie schon beim kgV kann man auch das Ergebnis des ggT schnell kontrollieren. So darf der ggT niemals größer als die kleinere der beiden Zahlen sein, und muss mindestens 1 sein.

Kleinste gemeinsame Vielfache (kgV)

Tatsächlich kann man den größten gemeinsamen Teiler auch mithilfe des kleinsten gemeinsamen Vielfachen ermitteln. Diese Vorgehensweise bietet sich besonders dann an, wenn sowohl das kgV als auch der ggT zu finden ist. Die Formel dafür ist folgende:

$$kgV(a, b)=\frac{a·b}{kgV(a, b)}$$ Sollte also der kgV von zwei Zahlen bereits bekannt oder schnell zu ermitteln sein, so kann man über diese Methode auf schnellem und einfachem Weg den ggT herausfinden.

Steinscher Algorithmus

Die dritte Methode zur Bestimmung des größten gemeinsamen Vielfachen nennt sich der steinsche Algorithmus (von Josef Stein) und beschreibt eine Vorgehensweise, die weniger von Menschen, als viel eher von Computerprogrammen umzusetzen ist. Es werden für diese Methode nur zwei Rechenoperationen benötigt, die Subtraktion und Division durch 2. Und so funktioniert der Algorithmus: Zunächst benötigt man eine Variable d, die den Wert 0 hat. In den folgenden Schritten werden a und b immer weiter verkleinert, bis irgendwann \(a=b\) gilt. In diesem Fall ist der Algorithmus beendet und das Ergebnis ist \(a·2^d\). Angenommen \(a=b\) gilt nicht am Anfang, so gibt es folgende vier Möglichkeiten:

Im ersten Fall ist 2 ein gemeinsamer Teiler von a und b. Deshalb teilt man beide Zahlen durch 2 und erhöht d um 1. Der zweite und dritte Fall sind eigentlich ein und der selbe Fall, da \(ggT(a, b)=ggT(b, a)\) gilt. Ist also eine der beiden Zahlen a und b gerade und die andere ungerade, so wird die gerade Zahl durch 2 geteilt, d bleibt unverändert. Im vierten Fall ist ein wenig mehr zutun: Eine der beiden Zahlen muss größer sein als die andere, da sonst die Endbedingung \(a=b\) erreicht wäre. Angenommen \(a>b\) (wenn \(b>a\) können a und b vertauscht werden), so gibt es ein \(c=a-b\). Über c lassen sich dann ein paar Aussagen treffen: c muss kleiner sein als a, aber trotzdem noch positiv. Und jeder gemeinsame Teiler von a und b muss auch ein Teiler von c sein, sodass gilt \(ggT(a, b)=ggT(a, c)=ggT(b, c)\). Beachtet man zudem die Tatsache, das c gerade ist, weil a und b beide ungerade sind, so kommt man zu dem Schluss, dass in den gerade aufgestellten Zusammenhängen c durch \(\frac{c}{2}\) ersetzt werden kann. Zusammengefasst gilt: \(ggT(a, b)=ggT(a, \frac{c}{2})=ggT(b, \frac{c}{2})\). Deshalb wird das a durch \(\frac{c}{2}\) ersetzt und dieser Schritt wird so lange wiederholt, bis \(a=b\) gilt. Das Ergebnis ist dass \(ggT(a, b)=a·2^d\)

Der steinsche Algorithmus ist deshalb so gut für Computer geeignet, da die notwendigen Operationen zu den einfachsten und schnellsten eines (binären) Computers gehören:

Wenn du mehr über den größten gemeinsamen Teiler erfahren willst, bist du hier genau richtig.

Deine Meinung ist wichtig!

Bitte teil mir mit, wie dir diese Seite gefällt, ob sie dir weitergeholfen hat und welche Themen du dir noch wünscht.