Euklidischer Algorithmus

In diesem Kapitel schauen wir uns an, was der euklidische Algorithmus ist.

Benötigtes Vorwissen

Euklidischer Algorithmus ist eine Bezeichnung für ein Rechenverfahren zur Berechnung des größten gemeinsamen Teilers zweier Zahlen.

Wortherkunft

Mathematiker verstehen unter einem „Algorithmus“ eine Vorschrift zur schematischen Lösung einer Aufgabe. Dieses Wort ist eine Latinisierung, also eine Übersetzung ins Lateinische, des Namens von al-Chwarizimi, dem Verfasser eines der ältesten Algebrabücher.

Der Entdecker des Algorithmus, mit dem wir uns in diesem Artikel beschäftigen, ist der griechische Mathematik Euklid. Deshalb heißt er euklidischer Algorithmus. Logisch, oder?

Vorgehensweise

Der euklidische Algorithmus führt in drei Schritten zur Lösung:

  1. Größere durch kleine Zahl dividieren
  2. Divisor durch Rest dividieren
  3. Ergebnis in mathematischer Schreibweise notieren

Erläuterung der einzelnen Schritte

Im 1. Schritt dividieren wir die größere durch die kleinere Zahl.

Im 2. Schritt dividieren wir den Divisor der vorherigen Division durch den Rest der vorherigen Division. Das machen wir solange, bis die Rechnung aufgeht - also kein Rest übrig bleibt.

Im 3. und letzten Schritt notieren wir das Ergebnis in mathematischer Schreibweise: Der größte gemeinsame Teiler der beiden Ausgangszahlen ist der Divisor der letzten Division (2. Schritt).

Beispiele

  • Berechne den größten gemeinsamen Teiler von \(16\) und \(24\).

    1) Größere durch kleinere Zahl dividieren
    \(24 : 16 = 1 \text{ Rest } 8\)

    2) Divisor durch Rest dividieren
    \(16 : \class{mb-green}{8} = 2\)

    3) Ergebnis in mathematischer Schreibweise notieren
    \(\text{ggT}(16, 24) = \class{mb-green}{8}\)

  • Berechne den größten gemeinsamen Teiler von \(132\) und \(150\).

    1) Größere durch kleinere Zahl dividieren
    \(150 : 132 = 1 \text{ Rest } 18\)

    2) Divisor durch Rest dividieren
    \(132 : 18 = 7 \text{ Rest } 6\)
    \(18 : \class{mb-green}{6} = 3\)

    3) Ergebnis in mathematischer Schreibweise notieren
    \(\text{ggT}(132, 150) = \class{mb-green}{6}\)

  • Berechne den größten gemeinsamen Teiler von \(255\) und \(442\).

    1) Größere durch kleinere Zahl dividieren
    \(442 : 255 = 1 \text{ Rest } 187\)

    2) Divisor durch Rest dividieren
    \(255 : 187 = 1 \text{ Rest } 68\)
    \(187 : 68 = 2 \text{ Rest } 51\)
    \(68 : 51 = 1 \text{ Rest } 17\)
    \(51 : \class{mb-green}{17} = 3\)

    3) Ergebnis in mathematischer Schreibweise notieren
    \(\text{ggT}(255, 442) = \class{mb-green}{17}\)

Anmerkung

Mit Hilfe des euklidischen Algorithmus können wir immer nur den ggT zweier Zahlen berechnen. Wenn du den ggT mehrerer Zahlen berechnen willst, empfiehlt sich eines der beiden anderen Verfahren, die ich im Kapitel über den größten gemeinsamen Teiler beschrieben habe.

Ausblick

Gilt \(\text{ggT}(a, b) = 1\), so heißen \(a\) und \(b\) teilerfremd, da in diesem Fall \(a\) und \(b\) außer der \(1\), die bekanntlich Teiler jeder natürlichen Zahl ist, keine weiteren gemeinsamen Teiler besitzen.

Andreas Schneider

Hat dir meine Erklärung geholfen?
Facebook Like Button
Lob, Kritik oder Anregungen? Schreib mir doch mal persönlich :)

Weiterhin viel Erfolg beim Lernen!

Andreas Schneider

Zum Kontaktformular