Der euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Mit ihm lässt sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen. Das Verfahren ist nach dem griechischen Mathematiker Euklid benannt, der es in seinem Werk „Die Elemente“ beschrieben hat.
Der größte gemeinsame Teiler zweier Zahlen kann auch aus ihren Primfaktorzerlegungen ermittelt werden. Ist aber von keiner der beiden Zahlen die Primfaktorzerlegung bekannt, so ist der euklidische Algorithmus das schnellste bekannte Verfahren zur Berechnung des größten gemeinsamen Teilers.
Der euklidische Algorithmus lässt sich nicht nur auf natürliche Zahlen anwenden. Vielmehr kann damit der größte gemeinsame Teiler von zwei Elementen eines jeden euklidischen Rings berechnet werden. Dazu zählen beispielsweise Polynome über einem Körper.
Der klassische Algorithmus
mini|280px|Beispiel: ggT(44,12) = 4
Euklid berechnete den größten gemeinsamen Teiler für die Längen zweier Linien, indem er nach einem gemeinsamen „Maß“ suchte, d. h. nach einer Strecke, von der die beiden Linien ganzzahlige Vielfache sind. Dazu zog er wiederholt die kleinere der beiden Längen von der größeren ab. Dabei nutzt er aus, dass sich der größte gemeinsame Teiler zweier Zahlen (oder Längen) nicht ändert, wenn man die kleinere von der größeren abzieht.
Ist die Differenz von und sehr groß, sind unter Umständen viele Subtraktionsschritte notwendig. Hippasos von Metapont benutzte schon vor Euklid diese so genannte Wechselwegnahme geometrisch für den Beweis der Inkommensurabilität bei gewissen regelmäßigen n-Ecken: Im Quadrat oder im regelmäßigen Fünfeck etwa gibt es keinen gemeinsamen Teiler (Maß) einer Seite mit der Diagonalen.
Heutzutage wird in der Regel der weiter unten beschriebene Divisions-Algorithmus verwendet, bei dem die Schritte 2 und 3 dadurch ersetzt werden, dass man, an Stelle der Differenz von und , für den Rest bei der Division von durch nimmt. Ein weiterer Vorteil dieser Variante ist, dass man sie auf beliebige euklidische Ringe (zum Beispiel Polynomringe über einem Körper) übertragen kann, in denen der klassische Algorithmus nicht funktioniert.
Beschreibung durch Pseudocode Der klassische Algorithmus hier in Pseudocode für nichtnegative ganze Zahlen a und b dargestellt:
EUCLID_OLD(a,b) 1 wenn a = 0 dann 2 Ergebnis = b 3 sonst 4 solange b ≠ 0 5 wenn a > b dann 6 a a – b 7 sonst 8 b b – a 9 // 10 // 11 Ergebnis = a 12 //
Dieser Algorithmus kann auch in einer rekursiven Version angegeben werden:
EUCLID_OLD_RECURSIVE(a,b) 1 wenn b = 0 dann 2 Ergebnis = a 3 sonst 4 wenn a = 0 dann 5 Ergebnis = b 6 sonst 7 wenn a > b dann 8 Ergebnis = EUCLID_OLD_RECURSIVE(a – b, b) 9 sonst 10 Ergebnis = EUCLID_OLD_RECURSIVE(a, b – a) 11 // 12 // 13 //
Moderner euklidischer Algorithmus Heutzutage ersetzt man die im klassischen Algorithmus auftretenden wiederholten Subtraktionen eines Wertes jeweils durch eine einzige Division mit Rest. Der moderne euklidische Algorithmus führt nun in jedem Schritt solch eine Division mit Rest aus. Er beginnt mit den beiden Zahlen und , deren größter gemeinsamer Teiler bestimmt werden soll.
In jedem weiteren Schritt wird mit dem Divisor und dem Rest des vorhergehenden Schritts eine erneute Division mit Rest durchgeführt, und zwar so lange, bis eine Division aufgeht, das heißt, der Rest Null ist.
Der Divisor der letzten Division ist dann der größte gemeinsame Teiler.
Da sich die Zahlen in jedem zweiten Schritt mindestens halbieren, ist das Verfahren auch bei großen Zahlen extrem schnell.
Beispiel mini|Animation des euklidischen Algorithmus für den größten gemeinsamen Teiler ggT(1071, 462) = 21. Der größte gemeinsame Teiler von und wird mit dem euklidischen Algorithmus wie folgt berechnet:
Der größte gemeinsame Teiler von und ist somit .
Ein weiteres Beispiel, aber in anderer Darstellung, findet man auf der Seite Division mit Rest im Abschnitt Euklidischer Algorithmus.
Beschreibung durch Pseudocode Im Folgenden wird der moderne Euklidische Algorithmus sowohl in einer rekursiven als auch einer iterativen Variante beschrieben. Dabei sind und jeweils die beiden Zahlen, deren größter gemeinsamer Teiler berechnet werden soll.
Rekursive Variante EUCLID(a,b) 1 wenn b = 0 dann 2 Ergebnis = a 3 sonst 4 Ergebnis = EUCLID(b, Divisionsrest(a durch b)) // siehe Modulo-Funktion 5 //
Iterative Variante EUCLID(a,b) 1 solange b ≠ 0 2 h Divisionsrest(a durch b) // Siehe Modulo-Funktion 3 a b 4 b h 5 // 6 Ergebnis = a
Korrektheit des Algorithmus In jedem Schritt des Algorithmus wird eine Division mit Rest ausgeführt:
.
Die Division mit Rest hat die Eigenschaft
.
Im letzten Schritt des Algorithmus,
,
ist und deshalb gilt
.
Da im ersten Schritt und ist, ist
.
Euklidischer Algorithmus für mehr als zwei Zahlen Wenn der größte gemeinsame Teiler von mehr als zwei Zahlen berechnet werden soll, wird der euklidische Algorithmus schrittweise auf jeweils zwei der Zahlen angewendet. Für den größten gemeinsamen Teiler gilt das Assoziativgesetz und das Kommutativgesetz. Daher gilt für beliebige natürliche Zahlen , ,
und allgemein für beliebige natürliche Zahlen
Historische Entwicklung mini|Darstellung Euklids von Justus von Gent (15. Jahrhundert)
Der euklidische Algorithmus ist der älteste bekannte nicht-triviale Algorithmus. Das Verfahren wurde von Euklid um 300 v. Chr. in seinem Werk Die Elemente beschrieben. In Buch VII (Propositionen 1 und 2) formulierte er den Algorithmus für positive ganze Zahlen und in Buch X (Proposition 2 und 3) für positive reelle Zahlen. Die letztere Version ist ein geometrischer Algorithmus und Euklid nannte ihn „Wechselwegnahme“ (griech. ἀνθυφαίρεσις anthyphairesis). Er suchte ein größtes gemeinsames „Maß“ zweier Strecken: eine dritte Strecke, sodass die Länge der beiden ursprünglichen Strecken Vielfache der Länge der dritten Strecke sind.
Das Verfahren wurde wahrscheinlich nicht von Euklid erfunden, da er in den Elementen die Erkenntnisse früherer Mathematiker zusammenfasste. Der Mathematiker und Historiker Bartel Leendert van der Waerden vermutet, dass Buch VII ein schon von den Pythagoreern verwendetes Lehrbuch der Zahlentheorie ist. Hippasos von Metapont führte etwa 500 v. Chr. vermutlich seinen Beweis der Inkommensurabilität von gewissen Strecken und Diagonalen auf Grundlage des euklidischen Algorithmus durch, und auch Eudoxos von Knidos (um 375 v. Chr.) kannte wohl das Verfahren. Aristoteles (um 330 v. Chr.) wies auf dieses Verfahren in seinem Werk Topik (158b, 29–35) hin.
Jahrhunderte später wurde der euklidische Algorithmus voneinander unabhängig in Indien und China entdeckt, um damit hauptsächlich diophantische Gleichungen aus der Astronomie zu lösen und genaue Kalender zu erstellen. Im fünften Jahrhundert beschrieb der indische Mathematiker und Astronom Aryabhata den Algorithmus als „Pulverisator“, wahrscheinlich aufgrund seiner Effektivität beim Lösen diophantischer Gleichungen. Zwar hat schon der chinesische Mathematiker und Astronom Sun Zi einen Spezialfall des chinesischen Restsatzes beschrieben, die allgemeine Lösung wurde jedoch von Qin Jiushao 1247 in seinem Buch Shushu Jiuzhang () veröffentlicht. Im neuzeitlichen Europa wurde der euklidische Algorithmus erstmals wieder in der zweiten Auflage von Bachets Problèmes plaisants et délectables, qui se font par les nombres beschrieben. Der Algorithmus wurde in Europa zum Lösen diophantischer Gleichungen und zur Berechnung der Kettenbruchentwicklung verwendet. Nicholas Saunderson veröffentlichte den erweiterten euklidischen Algorithmus und schrieb ihn Roger Cotes zu als Methode zur effizienten Berechnung von Kettenbrüchen.
Im 19. Jahrhundert gab der euklidische Algorithmus den Anstoß zur Entwicklung neuer Zahlensysteme wie den gaußschen Zahlen und den Eisenstein-Zahlen. 1815 verwendete Carl Friedrich Gauß den euklidischen Algorithmus, um die eindeutige Faktorisierung der gaußschen Zahlen zu zeigen. Seine Arbeit wurde jedoch erst im Jahr 1832 veröffentlicht.Carl Friedrich Gauß: Theoria residuorum biquadraticorum. Gauß erwähnte den Algorithmus zudem in seinem 1801 veröffentlichten Werk Disquisitiones Arithmeticae, allerdings nur als Methode zur Berechnung von Kettenbrüchen. Peter Gustav Lejeune Dirichlet scheint der Erste zu sein, der den euklidischen Algorithmus als Grundlage eines großen Teils der Zahlentheorie beschrieben hat. Er bemerkte, dass viele Ergebnisse der Zahlentheorie, wie beispielsweise die eindeutige Faktorisierung, auch für andere Zahlensysteme gelten, in denen der euklidische Algorithmus angewendet werden kann. Dirichlets Vorlesungen über Zahlentheorie wurden von Richard Dedekind herausgegeben und erweitert, der den euklidischen Algorithmus für das Studium algebraischer Zahlen nutzte, einer neuen allgemeineren Zahlenart. Dedekind war beispielsweise der Erste, der Pierre de Fermats Zwei-Quadrate-Satz mit der eindeutigen Faktorisierung der gaußschen Zahlen bewies. Dedekind führte das Konzept des euklidischen Rings ein, ein Zahlensystem, in dem eine verallgemeinerte Variante des euklidischen Algorithmus angewendet werden kann. In den letzten Jahrzehnten des 19. Jahrhunderts trat der euklidische Algorithmus allmählich hinter Dedekinds allgemeinere Theorie der Ideale zurück.
Jacques Charles François Sturm entwickelte 1829 die sturmschen Ketten zur Berechnung der Anzahl der Nullstellen eines Polynoms in einem vorgegebenen Intervall. Dabei wird eine Variante des euklidischen Algorithmus verwendet, um die einzelnen Glieder einer Kette zu bestimmen.
In der Vergangenheit gab es zahllose Versuche, den euklidischen Algorithmus auf mehr als zwei natürliche Zahlen zu verallgemeinern, beispielsweise um außer ihrem größten gemeinsamen Teiler auch optimale (etwa kleinstmögliche) Multiplikatoren zu finden, die in der Linearkombination mit den Zahlen diesen Teiler liefern. Der moderne Stand der Forschung hierzu wurde von Havas, Majewski und Matthews dargestellt.siehe etwa: George Havas, Bohdan S. Majewski, Keith R. Matthews: (PDF; 160 kB). Technical Report TR0302, The University of Queensland, Brisbane 1994. oder G. Havas, B. S. Majewski, K. R. Matthews: (PDF; 266 kB). Experimental Mathematics 7 (1998) No. 2, S. 125–136 und die reichhaltige Bibliografie darin