✖

Der größte gemeinsame Teiler

Der größte gemeinsame Teiler zweier ganzer Zahlen ist eine Zahl, die beide Zahlen ohne Rest teilt, und dennoch gibt es keine andere größere Zahl, die beide Zahlen ebenfalls ohne Rest teilt.

Betrachten wir zum Beispiel die Zahlen 24 und 32. Was ist ihr größter gemeinsamer Teiler? Zunächst einmal suchen wir nach der Zahl, die beide Zahlen teilt.

  • Zum Beispiel teilt die Zahl 12 zwar 24, aber nicht 32, weil 32 / 12 gleich 2,666 ist... was keine ganze Zahl ist. Die Zahl 12 kann also nicht der größte gemeinsame Teiler von 24 und 32 sein.
  • Was ist mit der Zahl 4? Sie teilt beide Zahlen, 24 / 4 ist gleich 6 und 32 / 4 ist gleich 8. Die Zahl 4 ist also unser erster Kandidat. Gibt es nicht eine größere Zahl, die beide Zahlen teilt?
  • Die Zahl 8 teilt sowohl 24 als auch 32, und sie ist größer als 4.
  • Es gibt keine Zahl, die größer als 8 ist und beide Zahlen teilt. Die Zahl 8 ist also der größte gemeinsame Teiler der Zahlen 24 und 32.

Euklids Algorithmus zur Ermittlung des größten gemeinsamen Teilers

Es gibt einen relativ einfachen Weg, den größten gemeinsamen Teiler zweier Zahlen mit Hilfe des Algorithmus von Euklid zu finden. Beginnen wir mit zwei Zahlen x und y, für die wir den größten gemeinsamen Teiler finden wollen. Als Beispiel versuchen wir es mit den Zahlen x = 50 und y = 35. Dann gehen wir wie folgt vor:

  1. Wir dividieren x / y und merken uns den Rest nach der Division. Diesen Rest notieren wir als z. Für unser Beispiel erhalten wir 50 / 35, was uns den Rest z = 15 liefert.
  2. Nun vertauschen wir die Variablen und speichern den Wert y in der Variablen x und den Wert z in y. Den ursprünglichen Wert x verwerfen wir. Nach diesem Schritt erhalten wir x = 35 und y = 15.
  3. Nun wollen wir sehen, ob y gleich Null ist. Wenn ja, ist der größte gemeinsame Teiler x. Da y nicht gleich Null ist, fahren wir fort und wiederholen das ganze Verfahren vom ersten Punkt an.
  4. Wir dividieren x / y erneut, d. h. wir dividieren 35 / 15, was uns den Rest nach der Division von z = 5 liefert.
  5. Durch Vertauschen der Variablen erhalten wir x = 15 und y = 5. Da y nicht gleich Null ist, fahren wir fort.
  6. Wir dividieren durch x / y, was 15 / 5 ergibt. Der Rest nach der Division ist z = 0.
  7. Wenn wir die Variablen vertauschen, erhalten wir x = 5 und y = 0.
  8. An diesem Punkt ist y = 0 gleich und unser Algorithmus endet. Der größte gemeinsame Teiler ist die Zahl x = 5.

Wichtig ist, dass die Reihenfolge der Zahlen keine Rolle spielt. Wenn wir die Zahlen aus dem Beispiel vertauschen würden, bekämen wir das Paar x = 35 und y = 50. Die Vorgehensweise wäre dieselbe:

  1. Dividieren Sie x / y, dann dividieren Sie 35 / 50, was den Rest z = 35 ergibt.
  2. Vertauschen Sie die Variablen x = 50 und y = 35.
  3. Wir sehen, dass wir nach diesem Schritt einfach die Inhalte der Variablen x und y miteinander vertauscht haben...

Rechner

Mit diesem Rechner können Sie den größten gemeinsamen Teiler berechnen.