Größter gemeinsamer Teiler (ggT) und kleinstes gemeinsames Vielfaches (kgV) nach oben

zum Text Definition der Begriffe
zum Text Primfaktorenzerlegung
zum Text Berechnung des ggT über die Primfaktorenzerlegung
zum Text Berechnung des kgV über die Primfaktorenzerlegung
zum Text Berechnung des ggT mit dem Algorithmus des Euklid
zum Text Berechnung des kgV mit Hilfe des ggT

Anna Heynkes, 23.12.2005

Definition der Begriffe nach oben

Größten gemeinsamen Teiler (ggT) von zwei oder mehr Zahlen nennt man die größte natürliche Zahl, durch die sich die zwei oder mehr Zahlen alle ohne Rest teilen lassen.

Kleinstes gemeinsames Vielfaches (kgV) von zwei oder mehr Zahlen nennt man die kleinste natürliche Zahl, die ein ganzzahliges Vielfaches dieser zwei oder mehr Zahlen ist.

Primfaktorenzerlegung nach oben

Sucht man den größten gemeinsamen Teiler oder das kleinste gemeinsame Vielfache für relativ kleine Zahlen, dann lässt sich dies einigermaßen leicht über eine so genannte Primfaktorenzerlegung erledigen. Dazu teilt man einfach die fraglichen Zahlen durch möglichst kleine Primzahlen, bis am Ende eine Primzahl übrig bleibt.

Beispiel:
90/2 = 45, 45/3 = 15, 15/3= 5
Demnach lässt sich die 90 auch als Produkt dieser Primfaktoren darstellen:
90 = 2 · 3 · 3 · 5 oder 21 · 32 · 51

Berechnung des ggT über die Primfaktorenzerlegung nach oben

Den größten gemeinsamen Teiler von nicht zu vielen relativ kleinen Zahlen kann man einigermaßen leicht finden, indem man diese Zahlen zunächst in ihre Primfaktoren zerlegt und diese Primfaktoren anschließend der Größe nach sortiert untereinander schreibt. Wenn man schon mit Potenzen rechnen kann, dann fasst man alle gleichen Primfaktoren zu Potenzen zusammen. Das erleichtert die Berechung, aber es geht auch ohne dies.

Beispiel: ggT von 60 und 90
60 = 2 · 2 · 3 · 5 oder 22 · 31 · 51
90 = 2 · 3 · 3 · 5 oder 21 · 32 · 51

Jetzt kann man den größten gemeinsamen Teiler ausrechnen, indem man das Produkt aller Primfaktoren bildet, die in beiden Primfaktorenzerlegungen auftraten. Wer schon mit Potenzen rechnen kann, bildet das Produkt der Primzahlpotenzen und nimmt dabei jeweils die kleinsten Hochzahlen.

Beispiel: ggT von 60 und 90
60 = 2 · 2 · 3 · 5
90 = 2 · 3 · 3 · 5
ggT = 2 · 3 · 5 = 30
oder etwas übersichtlicher mit Potenzen:
60 = 22 · 31 · 51
90 = 21 · 32 · 51
ggT = 21 · 31 · 51 = 30

Berechnung des kgV über die Primfaktorenzerlegung nach oben

Bei nicht zu vielen relativ kleinen Zahlen lässt sich auch das kleinste gemeinsame Vielfache ohne zu großen Aufwand mittels Primfaktorenzerlegung ermitteln. Der einzige Unterschied zur Berechnung des ggT besteht darin, dass man das Produkt aller Primzahlen bildet, die bei mindestens einer Primfaktorenzerlegung auftraten.

Beispiel: ggT von 60 und 90
60 = 2 · 2 · 3 · 5
90 = 2 · 3 · 3 · 5
kgV = 2 · 2 · 3 · 3 · 5 = 180
oder etwas übersichtlicher mit Potenzen:
60 = 22 · 31 · 51
90 = 21 · 32 · 51
kgV = 22 · 32 · 51 = 180

Berechnung des ggT mit dem Algorithmus des Euklid nach oben

Der Algorithmus des Euklid zur Berechnung des ggT war auch schon vor Euklid bekannt und soll der älteste bekannte Algorithmus überhaupt sein. Er verzichtet auf die Primfaktorzerlegung und zieht statt dessen solange immer wieder die kleinere Zahl von der größeren ab, bis Subtrahend und Ergebnis gleich groß sind. Nach jeder Subtraktion nimmt man den Subtrahenden und das Ergebnis und zieht in der nächsten Subtraktion wieder die kleinere von der größeren Zahl ab.

Beispiel: ggT von 80 und 110
110 - 80 = 30; 80 - 30 = 50; 50 - 30 = 20; 30 - 20 = 10; 20 - 10 = 10

Sind die beiden Zahlen sehr unterschiedlich groß, dann muss man wiederholt die kleinere von der größeren Zahl abziehen.

Beispiel: ggT von 90 und 20
90 - 20 = 70; 70 - 20 = 50; 50 - 20 = 30; 30 - 20 = 10; 20 - 10 = 10

Man zieht also in diesem Beispiel schrittweise viermal die 20 von der 90 ab und könnte statt 90-20-20-20-20=10 auch 90-4·20=10 rechnen. Woher aber weiß man, wie oft man die kleinere von der viel größeren Zahl abziehen kann? Man findet dies leicht heraus, indem man die größere durch die kleinere Zahl teilt. In diesem Fall würde man 90 durch 20 teilen und erhielte als Ergebnis 90/80 = 4 Rest 10. Die 20 steckt also viermal in der 90 und genau so oft müsste man die 20 von der 90 abziehen, bis man für den nächsten Rechenschritt einen anderen Subtrahenden braucht. Anstatt nun diese Division als Nebenrechnung durchzuführen, kann man sie auch direkt in den Algorithmus einbauen. Man teilt also die größere durch die kleinere Zahl und ersetzt dann die größere Zahl durch den bei der Division übrig bleibenden Rest.

Beispiel: ggT von 90 und 20
90 / 20 = 4 Rest 10; 20 - 10 = 10

Berechnung des kgV mit Hilfe des ggT nach oben

Wenn die Primfaktorzerlegung zu aufwändig zu werden droht, kann man zunächst den ggT mit dem Algorithmus des Euklid berechnen und anschließend das kgV nach folgender Formel aus dem ggT gewinnen:

kgV von a und b = | a · b | / ggT
Beispiel: kgv von 60 und 90
kgV = |60 · 90| / 30 = 5400 / 30 = 180

meine Startseite