Euklidischer Algorithmus

Zweck und Grundidee

Der euklidische Algorithmus ist ein Verfahren der Zahlentheorie zur Berechnung des größten gemeinsamen Teilers, kurz ggT, zweier natürlicher Zahlen. Der ggT ist die größte natürliche Zahl, die beide Zahlen ohne Rest teilt. Sind die Primfaktorzerlegungen der Zahlen nicht bekannt, ist der euklidische Algorithmus das schnellste bekannte Verfahren zur Bestimmung des ggT.

Die grundlegende Beobachtung lautet: Der größte gemeinsame Teiler zweier Zahlen ändert sich nicht, wenn man von der größeren Zahl die kleinere abzieht. Der klassische Algorithmus wiederholt deshalb diese Subtraktion, bis eine Zahl die andere teilt. Beispielsweise ist ggT(44,12) = 4.

Der heute übliche moderne Algorithmus fasst mehrere solche Subtraktionen durch eine Division mit Rest zusammen. Ausgehend von a und b = r₀ führt man nacheinander Divisionen der Form

a = q₁·r₀ + r₁, r₀ = q₂·r₁ + r₂, r₁ = q₃·r₂ + r₃, …, rₙ₋₁ = qₙ₊₁·rₙ + 0

aus. Dabei ist jeder Rest kleiner als der vorherige Divisor. Sobald der Rest 0 ist, ist der letzte von 0 verschiedene Rest rₙ der gesuchte größte gemeinsame Teiler: ggT(a,b) = rₙ. Das Verfahren lässt sich außer auf natürlichen Zahlen auch auf die Elemente jedes euklidischen Rings anwenden, beispielsweise auf Polynome über einem Körper.

Ablauf, Beispiel und Korrektheit

Für ggT(1071,462) ergibt sich:

1071 = 2·462 + 147 462 = 3·147 + 21 147 = 7·21 + 0

Der letzte Rest ungleich 0 ist 21, also gilt ggT(1071,462) = 21.

Die iterative Variante wiederholt, solange b ≠ 0, diese Schritte:

• h wird zum Divisionsrest von a durch b. • a wird durch b ersetzt. • b wird durch h ersetzt.

Nach dem Ende ist a das Ergebnis. Rekursiv wird dieselbe Regel als EUCLID(a,b) = EUCLID(b, Divisionsrest von a durch b) formuliert; für b = 0 lautet das Ergebnis a.

Die Korrektheit folgt aus der Eigenschaft jeder Division mit Rest

rᵢ₋₁ = qᵢ₊₁·rᵢ + rᵢ₊₁ mit 0 ≤ rᵢ₊₁ < rᵢ:

ggT(rᵢ₋₁,rᵢ) = ggT(rᵢ,rᵢ₊₁).

Der ggT bleibt also in jedem Schritt unverändert. Im letzten Schritt gilt rₙ₋₁ = qₙ₊₁·rₙ + 0 und damit ggT(rₙ,0) = rₙ. Folglich ist ggT(a,b) = rₙ.

Für mehr als zwei Zahlen wendet man den Algorithmus schrittweise auf Zahlenpaare an. Wegen des Assoziativ- und Kommutativgesetzes gilt beispielsweise

ggT(a,b,c) = ggT(a,ggT(b,c)) = ggT(ggT(a,b),c).

Allgemein kann man ggT(a₁,a₂,…,aₙ) berechnen, indem man zunächst ggT(a₁,a₂), dann den ggT dieses Ergebnisses mit a₃ und so weiter bestimmt.

Geschwindigkeit und wichtige Varianten

Der moderne euklidische Algorithmus ist auch bei großen Zahlen sehr schnell, weil sich die beteiligten Zahlen in jedem zweiten Schritt mindestens halbieren. Der ungünstigste Fall tritt bei zwei aufeinanderfolgenden Fibonacci-Zahlen auf: Dann ist der jeweilige Rest immer die nächstkleinere Fibonacci-Zahl. Im schlimmsten Fall beträgt die Zahl der Divisionen O(log(a·b)); dieser Logarithmus ist proportional zur Zahl der Eingabeziffern.

Bei naiver Division ergibt sich eine tatsächliche Laufzeit von O((log(a·b))³). Mit schnellen Verfahren für Multiplikation und Division, unter anderem schneller Fourier-Transformation und Newton-Verfahren, ergibt sich eine theoretische Untergrenze von Ω(n·log(n)), wobei n die maximale Ziffernzahl von a und b bezeichnet.

Für a > b > 0 endet das Verfahren nach höchstens

1 + log_Φ(b/ggT(a,b)) = 1 + ln(b/ggT(a,b))/ln(Φ)

Iterationsschritten, wobei Φ = (1+√5)/2 ≈ 1,6180 der Goldene Schnitt ist. Nach dem Satz von Lamé ist die Zahl der Iterationsschritte kleiner als das Fünffache der Anzahl der Dezimalstellen von min(a,b).

Der steinsche oder binäre euklidische Algorithmus vermeidet allgemeine Divisionen und verwendet nur Divisionen durch 2. Sein Leistungsvorteil auf realen Rechnern zeigt sich allerdings nur, wenn der verwendete Integertyp nicht breiter als ein Prozessorregister ist.

Beim erweiterten euklidischen Algorithmus werden die Quotienten der Zwischenschritte gespeichert. Dadurch erhält man ganze Zahlen s und t mit

ggT(a,b) = s·a + t·b.

Diese Darstellung ermöglicht insbesondere die Berechnung multiplikativer Inverser in Restklassenringen. Eine weitere Erweiterung berechnet effizient das Jacobi-Symbol und steht mit dem quadratischen Reziprozitätsgesetz in Verbindung.

Zusammenhang mit Kettenbrüchen

Die bei den Divisionen auftretenden Quotienten sind genau die Teilnenner der Kettenbruchzerlegung von a/b. Beim Beispiel

1071 = 1·1029 + 42, 1029 = 24·42 + 21, 42 = 2·21 + 0

entsteht deshalb

1071/1029 = [1;24,2].

Das Verfahren gilt auch für beliebige reelle Zahlen. Bei einem rationalen Verhältnis endet es und liefert einen endlichen Kettenbruch [q₀;q₁,…,qₙ]. Bei einem irrationalen Verhältnis endet es nicht; die Folge der Quotienten bildet dann einen unendlichen Kettenbruch. Beispiele sind Φ = [1;1,1,…] und √2 = [1;2,2,…].

Auf zwei reelle Zahlen a und b angewandt, sucht der Algorithmus eine reelle Zahl g, deren ganzzahlige Vielfache a und b sind. Dies entspricht der Suche nach ganzen Zahlen s und t mit s·a + t·b = 0. Anders als bei ganzen Zahlen sind die Reste reell, während die Quotienten weiterhin ganzzahlig sind. Endet der Algorithmus, ist a/b rational; endet er nicht, ist a/b irrational.

Übertragung auf Polynome und andere Strukturen

Der Algorithmus lässt sich auf verschiedene algebraische Strukturen übertragen, darunter Polynome, quadratische Zahlen, gaußsche und Eisenstein-Zahlen sowie nichtkommutative Hurwitzquaternionen. In solchen Strukturen kann er auch dazu dienen, eindeutige Faktorisierung nachzuweisen: Jedes Element lässt sich dann bis auf die jeweils zulässigen Einheiten eindeutig in irreduzible Elemente zerlegen.

Polynome in einer Variablen über einem Körper bilden einen euklidischen Ring, weil eine Polynomdivision mit Rest möglich ist. Für f = x⁴+x³+x+1 und g = x²−1 in ℝ[x] gilt:

x⁴+x³+x+1 = (x²+x+1)·(x²−1) + (2x+2), x²−1 = (½x−½)·(2x+2) + 0.

Damit ist 2x+2 beziehungsweise das dazu assoziierte Polynom x+1 ein größter gemeinsamer Teiler.

Bei Polynomen über einem faktoriellen Ring R ist eine gewöhnliche Division mit Rest nicht immer in R[x] möglich. Ein faktorieller Ring besitzt bis auf Einheiten eine eindeutige Primfaktorzerlegung. Sind f und g vom Grad d_f beziehungsweise d_g, ist g₀ der Leitkoeffizient von g und δ = d_f−d_g, so ermöglicht die Pseudodivision Polynome q,r ∈ R[x] mit

g₀^(δ+1)·f = q·g + r,

wobei der Grad von r kleiner als der Grad von g ist. Wiederholte Pseudodivision bestimmt den ggT, kann aber durch exponentiell wachsende Zwischenkoeffizienten ineffizient werden. Das Entfernen des Inhalts jedes Rests begrenzt dieses Wachstum, erfordert jedoch weitere ggT-Berechnungen in R. Effizienter ist das Subresultantenverfahren.

Gaußsche Zahlen und geschichtliche Einordnung

Eine gaußsche Zahl hat die Form g = a+b·i mit ganzen Zahlen a und b. Für zwei gaußsche Zahlen α und β ungleich 0 ist ihr größter gemeinsamer Teiler die gemeinsame Teilerzahl mit der größten Norm. Die Division mit Rest wird wie bei ganzen Zahlen wiederholt.

Für α = 32+9i und β = 4+11i endet die Rechnung mit dem letzten Rest −i. Daher sind α und β teilerfremd. Bei gaußschen Zahlen muss der letzte Rest in diesem Fall nicht 1 sein, sondern kann eine der vier Einheiten 1, −1, i oder −i sein.

Der euklidische Algorithmus ist der älteste bekannte nichttriviale Algorithmus. Euklid beschrieb ihn um 300 v. Chr. in „Die Elemente“: in Buch VII für positive ganze Zahlen und in Buch X als geometrische „Wechselwegnahme“ für positive reelle Zahlen beziehungsweise Strecken. Wahrscheinlich war das Verfahren schon früher bekannt; Hippasos von Metapont soll es etwa 500 v. Chr. bei Untersuchungen inkommensurabler Strecken verwendet haben.

Später wurde das Verfahren unabhängig in Indien und China entdeckt und unter anderem für diophantische Gleichungen und Kalenderrechnungen eingesetzt. Im 19. Jahrhundert trug es zur Untersuchung neuer Zahlensysteme bei. Carl Friedrich Gauß verwendete es 1815 zum Nachweis der eindeutigen Faktorisierung gaußscher Zahlen; diese Arbeit erschien 1832. Richard Dedekind führte das Konzept des euklidischen Rings ein, in dem eine verallgemeinerte Form des Algorithmus möglich ist.