Kapitel
Was ist der Euklidische Algorithmus?
Der Euklidische Algorithmus ist ein Verfahren zur Berechnung des größten gemeinsamen Teilers (g.g.T.) zweier Zahlen.
Euklid war ein griechischer Mathematiker, der verschiedene Daten in einem Werk namens "Elemente" zusammenfasste. Dieses Werk gilt als einer der Grundpfeiler der Mathematik, und Euklid als "Vater der Geometrie".
In Elementen erklärt Euklid, dass der größte gemeinsame Teiler zweier Zahlen gefunden werden kann, indem man die größere Zahl durch die kleinere Zahl teilt. Ist die Division ganzzahlig, ist der größte gemeinsame Teiler die kleinere Zahl. Ist die Division nicht ganzzahlig, nimmt man den Rest und teilt so oft wie nötig, bis eine Division ohne Rest möglich ist. Der größte gemeinsame Teiler ist die letzte Zahl, durch die geteilt werden kann.
Obwohl das Wort "Algorithmus" uns an komplexe Berechnungen denken lässt, die von Computern gelöst werden, ist die Berechnung in unserem Fall viel einfacher. Wir müssen lediglich die folgenden Schritte befolgen.
Schritte zur Durchführung des Euklidischen Algorithmus
1 Die größere Zahl wird durch die kleinere geteilt..
2 Wenn bei der Division kein Rest bleibt, ist der Divisor der ggT
3Wenn bei der Division ein Rest bleibt, teilen wir den Divisor durch den erhaltenen Rest und wiederholen diesen Vorgang, bis kein Rest mehr bleibt. Der ggT ist der letzte Divisor.
Beispiele für die Anwendung des Euklidischen Algorithmus
Berechne den ggT von 
und 
Finde den ggT von und Der erste Schritt besteht darin, durch zu teilen:
Wir multiplizieren die Zahl mit dem ganzzahligen Teil des Ergebnisses 
, das heißt durch 
:
Wir subtrahieren die Zahl 
von und erhalten:
Wir wiederholen die Schritte, nehmen den Divisor, die Zahl , und dividieren ihn durch den erhaltenen Rest. 
:
Der ggT von und ist der letzte Divisor, der uns ein Ergebnis ohne Rest liefert, nämlich .
Berechne den ggT von 
und 
Berechne den ggT von und . Wir wenden dieselben Schritte wie im vorherigen Beispiel an.
Der ggT ist der letzte Divisor, nämlich
Berechne den ggT von 
und 
Wir berechnen den ggT von und . Wir beginnen die Berechnungen mit denselben Schritten:
Der ggT von und ist 
Mit KI zusammenfassen:
Du findest diesen Artikel toll? Vergib eine Note!
Loading...
