✖

Größter gemeinsamer Teiler

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

Nehmen wir als Beispiel die Zahlen 24 und 32. Was ist ihr größter gemeinsamer Teiler? Wir suchen zuallererst eine Zahl, die beide Zahlen teilt.

  • Z. B. teilt die Zahl 12 zwar die Zahl 24, aber nicht die Zahl 32, denn 32 / 12 ist gleich 2,666…, was keine ganze Zahl ist. Die Zahl 12 kann also nicht der größte gemeinsame Teiler der Zahlen 24 und 32 sein.
  • Wie wäre es mit der Zahl 4? Die teilt beide Zahlen, 24 / 4 ist gleich 6 und 32 / 4 ist gleich 8. Die Zahl 4 ist also unser erster Kandidat. Gibt es eine größere Zahl, die beide Zahlen teilt?
  • Die Zahl 8 teilt sowohl die Zahl 24 als auch die Zahl 32 und ist zugleich größer als die Zahl 4.
  • Eine andere Zahl, die größer als 8 ist und beide Zahlen teilt, gibt es nicht. Die Zahl 8 ist also der größte gemeinsame Teiler der Zahlen 24 und 32.

Euklidischer Algorithmus zur Bestimmung des größten gemeinsamen Teilers

Es gibt einen verhältnismäßig einfachen Weg, den größten gemeinsamen Teiler zweier Zahlen mit dem euklidischen Algorithmus zu finden. Nehmen wir am Anfang zwei Zahlen x und y, für die wir den größten gemeinsamen Teiler finden wollen. Als Beispiel probieren wir es mit den Zahlen x = 50 und y = 35. Dann gehen wir folgendermaßen vor:

  1. Wir teilen x / y und merken uns den Rest der Division. Diesen Rest bezeichnen wir mit z. In unserem Beispiel erhalten wir 50 / 35, was den Rest z = 15 ergibt.
  2. Nun vertauschen wir die Variablen: In der Variablen x speichern wir den Wert von y und in y den Wert von z. Den ursprünglichen Wert von x verwerfen wir. Nach diesem Schritt erhalten wir x = 35 und y = 15.
  3. Nun schauen wir, ob y gleich null ist. Wenn ja, ist der größte gemeinsame Teiler die Zahl x. Da y nicht gleich null ist, machen wir weiter und wiederholen das ganze Verfahren von vorn beim ersten Punkt.
  4. Wir teilen wieder x / y, also 35 / 15, was den Rest der Division z = 5 ergibt.
  5. Wir vertauschen die Variablen, wir erhalten also x = 15 und y = 5. Da y nicht gleich null ist, machen wir weiter.
  6. Wir teilen x / y, also 15 / 5. Der Rest der Division ist z = 0.
  7. Wir vertauschen die Variablen und erhalten x = 5 und y = 0.
  8. Jetzt ist y = 0 und unser Algorithmus endet. Der größte gemeinsame Teiler ist die Zahl x = 5.

Wichtig ist, dass es auf die Reihenfolge der Zahlen nicht ankommt. Wenn wir die Zahlen aus dem Beispiel vertauschen würden, erhielten wir das Paar x = 35 und y = 50. Das Vorgehen wäre dasselbe:

  1. Wir teilen x / y, also 35 / 50, was den Rest z = 35 ergibt.
  2. Wir vertauschen die Variablen: x = 50 und y = 35.
  3. Wir sehen, dass wir nach diesem Schritt lediglich den Inhalt der Variablen x und y gegeneinander vertauscht haben …

Rechner

Dieser Rechner berechnet dir den größten gemeinsamen Teiler.