Euklidischer Algorithmus

Der sogenannte euklidische Algorthymus ist ein Verfahren zum Ermitteln des größten gemeinsamen Teilers (ggT) zweier Zahlen.

Da das kleinste gemeinsame Vielfache (kgV) zweier Zahlen der Quotient aus ihrem Produkt und ihrem ggT ist, lässt sich mit ihm auch das kgV ermitteln.
Beim euklidischer Algorithmus wird wie folgt verfahren:

Man teilt die größere durch die kleinere Zahl.
Geht die Division auf, ist der Divisor der ggT.
Geht die Division nicht auf, bleibt ein Rest. Dieser Rest ist der neue Divisor. Der alte Divisor wird zum Dividenden. Nun setzt man das Verfahren fort.
Nach endlich vielen Schritten erhält man den ggT.
In manchen Fällen ist dies die Zahl 1, dann sind die Ausgangszahlen teilerfremd.

Es ist der ggT von 544 und 391 gesucht.

544:391 = 1; Rest 153
391:153 = 2; Rest 85
153:85 = 1; Rest 68
85:68 = 1; Rest 17
68:17 = 4; Rest 0

Die Divison geht auf, der ggT von 544 und 391 ist 17.
Daraus folgt: Das kgV von 544 und 391 ist
(544391):17=12512.

Es ist der ggT von 13 und 7 gesucht.

13:7 = 1; Rest 6
7:6 = 1; Rest 1
6:1 = 6; Rest 0

Die Division geht auf, der ggT von 13 und 7 ist 1, d. h., 13 und 7 sind teilerfremd.
Daraus folgt: Das kgV von 13 und 7 ist das Produkt
713=91.

Lernhelfer-App für dein Smartphone oder Tablet

Learnattack

Gemeinsam zu besseren Noten!Kooperation mit Duden Learnattack

Lernvideos, interaktive Übungen und WhatsApp-Nachhilfe – jetzt Duden Learnattack 48 Stunden kostenlos testen.

Du wirst automatisch zu Learnattack weitergeleitet.
Lexikon Share
Beliebte Artikel
alle anzeigen

Einloggen