Euklidischer Algorithmus

Der Euklidische Algorithmus ist ein Verfahren zur Bestimmung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen a und b. Es ist der älteste bekannte Algorithmus der Welt, benannt nach dem griechischen Mathematiker Euklid, der ihn um 300 vor Christus in seinem Werk Die Elemente angegeben hat. Das Verfahren war jedoch schon früher bekannt. Euklid nannte es antenaresis.

Das Prinzip des Euklidischen Algorithmus wird auch gegenseitige Wechselwegnahme genannt. Eingangsgrößen sind zwei natürliche Zahlen a und b, wobei a ≥ b sein muss. Bei der Berechnung verfährt man nach Euklid wie folgt:

1. setze m = a; n = b
2. berechne r = m - n
3. setze m = n, n = r
4. ist n ≠ 0 fahre fort mit Schritt 2

Nach Ablauf des Verfahrens hat man mit m den ggT von a und b gefunden.

Ist die Differenz von a und b sehr groß, sind unter Umständen sehr viele Subtraktionsschritte notwendig. Oftmals wird Schritt 2 deshalb dadurch ersetzt, dass man statt der Subtraktion r als Divistionsreset von a und b nimmt. In dem Fall muss auch nicht a ≥ b gefordert werden, da sich die Zahlen gegebenfalls verfahrensbedingt vertauschen. Ein weiterer Vorteil dieser Variante ist, dass man sie auf andere algebraische Strukturen (zum Beispiel Polynomringe, siehe Ringtheorie) übertragen kann, in denen der klassische Algorithmus nicht funktioniert.

Mit dem Euklidischen Algorithmus kann man den ggT mit verhältnismäßig gerigem Aufwand (im Vergleich zur Primfaktorzerlegung berechnen. Bei der Laufzeitanalyse stellt sich heraus, dass der schlimmste Eingabefall zwei aufeinander folgende Fibonacci-Zahlen sind.

Ein Problem bei der Umsetzung ist jedoch die Division, die unter Umständen einen hohen Rechenaufwand bedeutet. Für die Implementation auf Computern ist deshalb der binäre euklidische Algorithmus besonders geeignet. Er verwendet nur Subtraktion und die im Binärsystem besonders einfach durchzuführende Division durch 2.

1. setze m = a; n = b
2. dividiere m und n durch 2 solange, bis eine der beiden Zahlen ungerade ist. Die Zahl der notwendigen Divisionsschritte sei k
3. dividiere m durch 2, bis m ungerade ist
4. ist m<n, so vertausche diese Zahlen
5. setze m = m - n
6. ist m ≠ 0, dann fahre fort mit Schritt 3.

Nach Ablauf erhält man ggT(a,b) = n·2^k.

Hinter dem binären euklidischen Algorithmus steckt die Tatsache, dass 2 kein Faktor des ggT zweier Zahlen sein kann, wenn mindestens eine der beiden ungerade ist. Aus einer geraden Zahl kann man also so lange 2 ausdividieren, bis diese ungerade wird. Dies geschieht in Schritt 3. In Schritt 5 wird nun immer von einer ungeraden Zahl eine ungerade Zahl abgezogen. Das Ergebnis ist eine gerade Zahl, aus der man nun wieder 2 ausdividieren kann.

Das einzige Problem ergibt sich bei der Eingabe zweier gerader Zahlen. Hier muss man im Voraus entsprechend oft 2 ausdivieren (Schritt 2), was nach Beendigung des Algorithmus wieder rückgängig gemacht werden muss.

Erweiterungen des Euklidischen Algorithmus werden nicht nur zur Bestimmung des ggT verwendet, sondern z.B. auch zur Bestimmung von inversen in endlichen Gruppen, Kettenbruchzerlegung oder Berechnung des Jacobi-Symbols.

siehe auch: kgV und ggT