Euklidischer Algorithmus
In diesem Kapitel schauen wir uns an, was der euklidische Algorithmus ist.
Erforderliches Vorwissen
Definition
Euklidischer Algorithmus ist die 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 Kapitel beschäftigen, ist der griechische Mathematik Euklid. Daher der Name euklidischer Algorithmus
.
Anleitung
Größere durch kleinere Zahl dividieren
Divisor durch Rest dividieren
Ergebnis aufschreiben
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$.
Größere durch kleinere Zahl dividieren
$$ 24 : 16 = 1 \text{ Rest } 8 $$
Divisor durch Rest dividieren
$$ 16 : \class{mb-green}{8} = 2 $$
Ergebnis aufschreiben
$$ \text{ggT}(16, 24) = \class{mb-green}{8} $$
Berechne den größten gemeinsamen Teiler von $132$ und $150$.
Größere durch kleinere Zahl dividieren
$$ 150 : 132 = 1 \text{ Rest } 18 $$
Divisor durch Rest dividieren
$$ 132 : 18 = 7 \text{ Rest } 6 $$
$$ 18 : \class{mb-green}{6} = 3 $$
Ergebnis aufschreiben
$$ \text{ggT}(132, 150) = \class{mb-green}{6} $$
Berechne den größten gemeinsamen Teiler von $255$ und $442$.
Größere durch kleinere Zahl dividieren
$$ 442 : 255 = 1 \text{ Rest } 187 $$
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 $$
Ergebnis aufschreiben
$$ \text{ggT}(255, 442) = \class{mb-green}{17} $$
Anmerkung
Mithilfe 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.
