Größter gemeinsamer Teiler (ggT) und kleinstes gemeinsames Vielfaches (kgV)
	Definition der Begriffe
	Primfaktorenzerlegung
	Berechnung des ggT über die Primfaktorenzerlegung
	Berechnung des kgV über die Primfaktorenzerlegung
	Berechnung des ggT mit dem Algorithmus des Euklid
	Berechnung des kgV mit Hilfe des ggT

Anna Heynkes, 23.12.2005

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.

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.

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.

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.

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.

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.

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

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.

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:

meine Startseite