Euklidischer Algorithmus

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

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 

Beispiel 1 

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} $$

Beispiel 2 

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} $$

Beispiel 3 

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.

Noch Fragen? Logo von Easy-Tutor hilft!

Probestunde sichern