Euklidischer Algorithmus

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 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

„Wenn CD aber AB nicht misst, und man nimmt bei AB, CD abwechselnd immer das kleinere vom größeren weg, dann muss (schließlich) eine Zahl übrig bleiben, die die vorangehende misst.“

– Euklid: Die Elemente, Herausgegeben von Clemens Thaer, Wissenschaftliche Buchgesellschaft Darmstadt, VII Buch, § 2

Euklid berechnete den größten gemeinsamen Teiler, indem er nach einem gemeinsamen „Maß“ für die Längen zweier Linien suchte. 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 $a$ und $b$ 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 $m$ und $n$ , für $r$ den Rest bei der Division von $m$ durch $n$ 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  $\leftarrow$  a – b
7      sonst
8        b  $\leftarrow$  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 $a$ und $b=r_{0}$ , deren größter gemeinsamer Teiler bestimmt werden soll.

a=q_{1}\cdot r_{0}+r_{1}

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.

r_{0}=q_{2}\cdot r_{1}+r_{2}

r_{1}=q_{3}\cdot r_{2}+r_{3}

\vdots

r_{n-1}=q_{n+1}\cdot r_{n}+0

Der Divisor $r_{n}$ der letzten Division ist dann der größte gemeinsame Teiler.

\operatorname {ggT} (a,b)=r_{n}

Da sich die Zahlen in jedem zweiten Schritt mindestens halbieren, ist das Verfahren auch bei großen Zahlen extrem schnell.

Beispiel

Der größte gemeinsame Teiler von $\color {OliveGreen}1071$ und $\color {BurntOrange}462$ wird mit dem euklidischen Algorithmus wie folgt berechnet:

{\begin{array}{rcll}{\color {OliveGreen}1071}&=&2\cdot {\color {BurntOrange}462}&+&{\color {MidnightBlue}147}\\{\color {BurntOrange}462}&=&3\cdot {\color {MidnightBlue}147}&+&{\color {OrangeRed}21}\\{\color {MidnightBlue}147}&=&7\cdot {\color {OrangeRed}21}&+&0\end{array}}

Der größte gemeinsame Teiler von $\color {OliveGreen}1071$ und $\color {BurntOrange}462$ ist somit $\color {OrangeRed}21$ .

Beschreibung durch Pseudocode

Im Folgenden wird der moderne Euklidische Algorithmus sowohl in einer rekursiven als auch einer iterativen Variante beschrieben. Dabei sind $a$ und $b$ 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  $\leftarrow$  Divisionsrest(a durch b)        // Siehe Modulo-Funktion
3      a  $\leftarrow$  b
4      b  $\leftarrow$  h
5  //
6  Ergebnis = a

Programmierung

Das folgende Programm in der Programmiersprache C++ zeigt die Implementierung der rekursiven Variante und der iterativen Variante. Die zwei Varianten werden jeweils in einer Funktion mit den Parametern a und b implementiert. Bei der Ausführung des Programms wird die Hauptfunktion main verwendet, die die Eingabe der beiden Zahlen über die Konsole ermöglicht und dann das Ergebnis der beiden Varianten dort ausgibt.

#include <iostream>
using namespace std;

int gcdRecursive(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcdRecursive(b, a % b); // Rekursiver Aufruf der Methode
    }
}

int gcdIterative(int a, int b)
{
    if (a == 0)
    {
        return b;
    }
    while (b != 0)
    {
        int h = a % b;
        a = b;
        b = h;
    }
    return a;
}

// Hauptfunktion die das Programm ausführt
int main()
{
    int a, b; // Deklaration der lokalen Variablen
    cout << "Erste Zahl: "; // Ausgabe auf der Konsole
    cin >> a; // Eingabe über die Konsole
    cout << "Zweite Zahl: "; // Ausgabe auf der Konsole
    cin >> b; // Eingabe über die Konsole
    cout << "Größter gemeinsamer Teiler (rekursiv): " << gcdRecursive(a, b) << endl; // Aufruf der rekursiven Funktion
    cout << "Größter gemeinsamer Teiler (iterativ): " << gcdIterative(a, b) << endl; // Aufruf der íterativen Funktion
}

Korrektheit des Algorithmus

In jedem Schritt des Algorithmus wird eine Division mit Rest ausgeführt:

r_{i-1}=q_{i+1}\cdot r_{i}+r_{i+1},\qquad 0\leq r_{i+1}<r_{i}

Die Division mit Rest hat die Eigenschaft

\operatorname {ggT} (r_{i-1},r_{i})=\operatorname {ggT} (r_{i},r_{i+1})

Im letzten Schritt des Algorithmus,

r_{n-1}=q_{n+1}\cdot r_{n}+0

ist $r_{n+1}=0$ und deshalb gilt

\operatorname {ggT} (r_{n-1},r_{n})=\operatorname {ggT} (r_{n},0)=r_{n}

Da im ersten Schritt $r_{i-1}=a$ und $r_{i}=b$ ist, ist

\operatorname {ggT} (a,b)=r_{n}

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 $a$ , $b$ , $c$

\operatorname {ggT} (a,b,c)=\operatorname {ggT} (a,\operatorname {ggT} (b,c))=\operatorname {ggT} (\operatorname {ggT} (a,b),c)=\operatorname {ggT} (\operatorname {ggT} (a,c),b)

und allgemein für beliebige natürliche Zahlen $a_{1},a_{2},a_{3},\ldots ,a_{n}$

\operatorname {ggT} (a_{1},a_{2},a_{3},\ldots ,a_{n-1},a_{n})=\operatorname {ggT} (\ldots \operatorname {ggT} (\operatorname {ggT} (a_{1},a_{2}),a_{3})\ldots ,a_{n})

Historische Entwicklung

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 (chinesisch 數書九章 / 数书九章 – „Mathematische Abhandlung in neun Kapiteln“) 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. 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.

Der euklidische Algorithmus war der erste Algorithmus zur Berechnung von Ganzzahlbeziehungen kommensurabler reeller Zahlen. In den vergangenen Jahren wurden weitere Algorithmen für diese Aufgabenstellung entwickelt, beispielsweise der Ferguson–Forcade-Algorithmus aus dem Jahr 1979 und verwandte Algorithmen, der LLL-Algorithmus, der HJLS-Algorithmus (nach den Autoren Håstad, Just, Lagarias und Schnorr) und der PSLQ-Algorithmus (nach partial sum of squares plus LQ matrix decomposition). Im Jahr 2001 wurde gezeigt, dass die von einigen Autoren berichtete Instabilität des HJLS-Algorithmus lediglich auf einer unzweckmäßigen Implementierung beruhte und dass dieser Algorithmus äquivalent zum PSLQ-Algorithmus ist. Enger an den eigentlichen euklidischen Algorithmus angelehnt sind seine mehrdimensionalen Verallgemeinerungen von George Szekeres (1970), Helaman Ferguson und Rodney Forcade (1981), Just (1992), von Rössner und Schnorr (1996) sowie der sehr allgemeine Ansatz von Lagarias (1994).

1969 entwickelten Cole und Davie das Zwei-Spieler-Spiel „Euklid“, das auf dem euklidischen Algorithmus basiert. Bei diesem Spiel gibt es eine optimale Strategie. Die beiden Spieler beginnen mit zwei Stapeln von $a$ und $b$ Steinen. In jeder Runde nimmt ein Spieler $m$ -mal so viele Steine vom größeren Stapel, wie der kleinere Stapel groß ist. Auf diese Weise kann der nächste Spieler den größeren Stapel mit $x$ Steinen auf $x-my$ Steine verkleinern, wobei $y$ die Größe des kleineren Stapels ist. Es gewinnt der Spieler, der einen Stapel komplett abträgt.

Laufzeitanalyse

Mit dem euklidischen Algorithmus kann man den größten gemeinsamen Teiler mit verhältnismäßig geringem Aufwand (im Vergleich zur Berechnung der Primfaktorzerlegung der Zahlen $a$ und $b$ ) berechnen. Bei der Laufzeitanalyse stellt sich heraus, dass der ungünstigste Fall (Worst case) für die Eingabe zwei aufeinander folgende Fibonacci-Zahlen sind. Bei aufeinander folgenden Fibonacci-Zahlen ergibt sich als Rest immer die nächstkleinere Fibonacci-Zahl. Die Anzahl der benötigten Divisionen beträgt im schlimmsten Fall ${\mathcal {O}}(\log({a\cdot b}))$ , wobei $\log({a\cdot b})$ proportional zur Anzahl der Ziffern in der Eingabe ist (siehe Landau-Symbole).

Da die für die Division zweier Zahlen benötigte Zeit ihrerseits von der Anzahl der Ziffern der Zahlen abhängt, ergibt sich eine tatsächliche Laufzeit von ${\mathcal {O}}((\log({a\cdot b}))^{3})$ bei naiver Ausführung der Division. Durch die vollständige Überführung der eigentlichen Berechnung in den Frequenzbereich mittels einer speziellen schnellen Fourier-Transformation, wie sie im Schönhage-Strassen-Algorithmus Verwendung findet, schneller Reziprokwertberechnung mit dem Newton-Verfahren (im Frequenzbereich) für die Division und anschließender Rücktransformation mittels inverser schneller Fourier-Transformation kommt man so zu einer theoretischen Untergrenze von ${\mathcal {\Omega }}(n\cdot \log(n))$ , wobei $n$ die maximale Anzahl an Ziffern von $a$ und $b$ ist.

Die von Schönhage entwickelte Variante des euklidischen Algorithmus konnte durch Parallelisierung auf einem Multiprozessorsystem weiter beschleunigt werden.

Für die Anzahl der Schritte gibt es asymptotische Abschätzungen, wobei die Porter-Konstante eine Rolle spielt.

Wenn $a>b>0$ gilt und der euklidische Algorithmus $k$ Schritte braucht, gilt $a\geq f_{n+2}$ und $b\geq f_{n+1}$ mit den Fibonacci-Zahlen $f_{n+2}$ und $f_{n+1}$ . Für die Fibonacci-Zahl $f_{n+1}$ und die Goldene Zahl $\Phi :={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}6180$ :={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}6180} gilt die Ungleichung $f_{n+1}\geq \Phi ^{n-1}$ . Daraus folgt, dass der euklidische Algorithmus nach höchstens

1+\log _{\Phi }\left({\frac {b}{\operatorname {ggT} (a,b)}}\right)=1+{\tfrac {\ln \left({\tfrac {b}{\operatorname {ggT} (a,b)}}\right)}{\ln(\Phi )}}

Iterationsschritten beendet ist.

Nach dem Satz von Lamé gilt außerdem: Die Anzahl der Iterationsschritte des euklidische Algorithmus ist kleiner als das 5-fache der Anzahl der Dezimalstellen des Minimums von $a$ und $b$ .

Euklidischer Algorithmus und Kettenbruchzerlegung

Die Quotienten, die im euklidischen Algorithmus auftreten, sind genau die Teilnenner, die in der Kettenbruchzerlegung von ${\frac {a}{b}}$ vorkommen. Hier für das obige Beispiel mit hervorgehobenen Ziffern:t

Hieraus lässt sich der Kettenbruch entwickeln:

{\frac {1071}{1029}}=\mathbf {1} +{\frac {42}{1029}}=\mathbf {1} +{\frac {1}{\frac {1029}{42}}}=\mathbf {1} +{\frac {1}{\mathbf {24} +{\frac {21}{42}}}}=\mathbf {1} +{\frac {1}{\mathbf {24} +{\frac {1}{\mathbf {2} }}}}=[1;24,2]

Dieses Verfahren lässt sich auch für jede beliebige reelle Zahl $r$ anwenden. Ist $r$ nicht rational, so endet der Algorithmus einfach nie. Die so gewonnene Folge an Quotienten stellt dann die unendliche Kettenbruchzerlegung von $r$ dar.

Andere Zahlenmengen und algebraische Strukturen

Wie oben beschrieben wird der euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers zweier natürlicher Zahlen verwendet. Der Algorithmus lässt sich jedoch auch auf reelle Zahlen und exotischere algebraische Strukturen wie Polynome, quadratische Zahlen, Gaußsche Zahlen, Eisenstein-Zahlen und die nicht-kommutativen Hurwitzquaternionen verallgemeinern. Im letzten Fall wird der euklidische Algorithmus dazu verwendet, die wichtige Eigenschaft einer eindeutigen Faktorisierung zu zeigen. Das heißt, dass eine solche Zahl eindeutig in irreduzible Elemente, der Verallgemeinerung von Primzahlen, zerlegt werden kann. Die eindeutige Faktorisierung ist grundlegend für viele Beweise der Zahlentheorie.

Rationale und reelle Zahlen

Wie schon von Euklid im Buch 10 seines Werks „Die Elemente“ beschrieben, kann der euklidische Algorithmus auch auf reelle Zahlen angewandt werden. Das Ziel des Algorithmus ist es dann, eine reelle Zahl $g$ zu finden, sodass die beiden Zahlen $a$ und $b$ ganzzahlige Vielfache dieser Zahl sind. Diese Aufgabenstellung ist gleichbedeutend mit der Suche nach einer Ganzzahlbeziehung zwischen den beiden reellen Zahlen $a$ und $b$ , also der Berechnung zweier ganzer Zahlen $s$ und $t$ , für die $s\cdot a+t\cdot b=0$ gilt. Euklid verwendete diesen Algorithmus bei der Betrachtung der Inkommensurabilität von Strecken.

Der euklidische Algorithmus für reelle Zahlen unterscheidet sich in zwei Punkten von seinem Gegenstück für ganze Zahlen. Zum einen ist der Rest $r_{k}$ eine reelle Zahl, obwohl die Quotienten $q_{k}$ weiterhin ganze Zahlen sind. Zum anderen endet der Algorithmus nicht immer nach einer endlichen Anzahl von Schritten. Wenn er dies jedoch tut, dann ist der Bruch ${\tfrac {a}{b}}$ eine rationale Zahl; es gibt also zwei ganze Zahlen $m$ und $n$ mit

{\frac {a}{b}}={\frac {m\cdot g}{n\cdot g}}={\frac {m}{n}}

und kann als Kettenbruch $[q_{0};q_{1},q_{2},\ldots ,q_{N}]$ geschrieben werden. Wenn der Algorithmus nicht endet, dann ist der Bruch ${\tfrac {a}{b}}$ eine irrationale Zahl und mit dem unendlichen Kettenbruch $[q_{0};q_{1},q_{2},\ldots ]$ identisch. Beispiele für unendliche Kettenbrüche sind die Goldene Zahl $\Phi =[1;1,1,\ldots ]$ und die Wurzel aus 2 ${\sqrt {2}}=[1;2,2,\ldots ]$ . Im Allgemeinen ist es unwahrscheinlich, dass der Algorithmus anhält, da fast alle Verhältnisse ${\tfrac {a}{b}}$ zweier reeller Zahlen irrationale Zahlen sind.

Polynome

Polynome in einer Variablen über einem Körper bilden einen euklidischen Ring. Die Polynomdivision ist für diese Polynome also eine Division mit Rest und der euklidische Algorithmus kann genauso wie bei den ganzen Zahlen durchgeführt werden. Die Berechnung des größten gemeinsamen Teilers der Polynome $f=x^{4}+x^{3}+x+1$ und $g=x^{2}-1$ in $\mathbb {R} [x]$ gestaltet sich beispielsweise folgendermaßen:

x^{4}+x^{3}+x+1=\left(x^{2}+x+1\right)\cdot \left(x^{2}-1\right)+\left(2\cdot x+2\right)

x^{2}-1=\left({\frac {1}{2}}\cdot x-{\frac {1}{2}}\right)\cdot (2\cdot x+2)+0

Damit ist $2\cdot x+2$ (oder das dazu assoziierte Polynom $x+1$ ) ein größter gemeinsamer Teiler von $f$ und $g$ .

Polynome mit Koeffizienten aus einem faktoriellen Ring

Wir halten einen faktoriellen Ring (d. h. einen Ring mit bis auf Einheiten eindeutiger Primfaktorzerlegung) $R$ fest und betrachten Polynome aus dem Polynomring $R[x]$ , also Polynome in einer Variablen $x$ mit Koeffizienten aus $R$ . Im Spezialfall $R=k[y]$ , wobei $k$ ein Körper sei, erhalten wir so den Ring $k[x,y]$ der Polynome in zwei Variablen über $k$ .

In $R[x]$ ist Division mit Rest nicht mehr allgemein durchführbar. Seien z. B. $f=x^{2}+1$ und $g=2\cdot x+1$ in $\mathbb {Z} [x]$ . Polynomdivision in $\mathbb {Q} [x]$ liefert den Quotienten ${\tfrac {1}{2}}\cdot x-{\tfrac {1}{4}}$ , der nicht in $\mathbb {Z} [x]$ liegt. Wir können allerdings eine Pseudodivision wie folgt definieren: Seien $f$ und $g$ Polynome aus $R[x]$ mit Grad $d_{f}$ bzw. $d_{g}$ , sei $g_{0}$ der Leitkoeffizient des Polynoms $g$ , und $\delta :=d_{f}-d_{g}$ :=d_{f}-d_{g}} . Dann gibt es Polynome $q,r\in R[x]$ , so dass

g_{0}^{\delta +1}\cdot f=q\cdot g+r,

wobei wieder $r$ von geringerem Grad ist als $g$ . Durch wiederholte Durchführung der Pseudodivision lässt sich der ggT von $f$ und $g$ bestimmen, allerdings ist das Verfahren in der Praxis ineffizient, da die Faktoren $g_{0}^{\delta +1}$ die Koeffizienten der Zwischenergebnisse exponentiell anwachsen lassen. Um das zu vermeiden kann nach jedem Schritt der Inhalt des Rests $r$ entfernt werden, was allerdings wiederum ggT-Berechnungen in $R$ erfordert. Effizienter lässt sich der ggT mit dem Subresultantenverfahren berechnen.

Gaußsche Zahlen

Eine gaußsche Zahl $g$ ist durch $g=a+b\cdot {\mathrm {i} }$ gegeben, wobei $a$ und $b$ ganze Zahlen sind.

Sind $\alpha$ und $\beta$ gaußsche Zahlen, die beide nicht 0 sind. Der größte gemeinsame Teiler von $\alpha$ und $\beta$ ist die gaußsche Zahl mit der größten Norm, die sowohl ein Teiler von $\alpha$ als auch von $\beta$ ist.

Beispiel

Gesucht ist der größte gemeinsame Teiler von $\alpha =32+9\cdot {\mathrm {i} }$ und $\beta =4+11\cdot {\mathrm {i} }$ . In jedem Schritt wird mit dem Divisor und dem Rest des vorhergehenden Schritts eine erneute Division mit Rest durchgeführt, und zwar so lange, bis der Rest gleich 0 ist.

{\begin{aligned}32+9\cdot {\mathrm {i} }&=(4+11\cdot {\mathrm {i} })\cdot (2-2\cdot {\mathrm {i} })+2-5\cdot {\mathrm {i} }\\4+11\cdot {\mathrm {i} }&=(2-5\cdot {\mathrm {i} })\cdot (-2+{\mathrm {i} })+3-{\mathrm {i} }\\2-5\cdot {\mathrm {i} }&=(3-{\mathrm {i} })\cdot (1-{\mathrm {i} })-i\\3-{\mathrm {i} }&=(-{\mathrm {i} })\cdot (1+3\cdot {\mathrm {i} })+0\\\end{aligned}}

Der letzte Rest ungleich 0 ist $-{\mathrm {i} }$ , so dass $\alpha$ und $\beta$ nur Einheiten als gemeinsamen Teiler haben. Sie sind also teilerfremd. Im Gegensatz zu den ganzen Zahlen muss bei zwei gaußschen Zahlen, die teilerfremd sind, nicht unbedingt 1 der letzte Rest ungleich 0 sein. Es kann stattdessen eine der vier Einheiten $1$ , $-1$ , ${\mathrm {i} }$ , $-{\mathrm {i} }$ sein.

Varianten

Von Josef Stein stammt der nach ihm benannte steinsche Algorithmus, der ohne die aufwändigen Divisionen auskommt. Er verwendet nur noch Divisionen durch Zwei, die von einem Rechner sehr schnell durchzuführen sind. Aus diesem Grund wird dieser Algorithmus auch binärer euklidischer Algorithmus genannt. Der Performancevorteil auf realen Rechnern zeigt sich aber nur, wenn der Integertyp die Registerbreite des Prozessors nicht überschreitet.

Merkt man sich beim euklidischen Algorithmus die Quotienten $q_{i}$ der Zwischenschritte, dann lässt sich damit eine Darstellung

\operatorname {ggT} (a,b)=s\cdot a+t\cdot b

mit ganzen Zahlen $s$ und $t$ finden. Dies nennt man den erweiterten euklidischen Algorithmus. Damit lassen sich die Inversen in Restklassenringen berechnen.

Eine andere Erweiterung ist der Algorithmus, der hinter dem Quadratischen Reziprozitätsgesetz steckt. Mit diesem lässt sich das Jacobi-Symbol effizient berechnen.

Siehe auch

Erweiterter euklidischer Algorithmus
Steinscher Algorithmus

Weblinks

Wikibooks: Algorithmensammlung zum euklidischen Algorithmus – Lern- und Lehrmaterialien

Christian Spannagel: Der Euklidische Algorithmus. Vorlesungsreihe, 2012.
Peter Zierenberg: Euklidischer Algorithmus – C++
Hochschule Flensburg: Erweiterter euklidischer Algorithmus
www.tutorialspoint.com: Program to Find GCD of Two Numbers Using Recursive Euclid Algorithm
GeeksforGeeks: Euclidean algorithms (Basic and Extended)

Einzelnachweise

[1]
Bartel Leendert van der Waerden: Erwachende Wissenschaft. Ägyptische, babylonische und griechische Mathematik. Birkhäuser Verlag, Basel 1956, S. 188.
[2]
Donald E. Knuth: The Art of Computer Programming. 3. Auflage. Band 2: Seminumerical Algorithms. Addison-Wesley Professional, 1997, ISBN 0-201-89684-2, S. 334–337.
[3]
John Stillwell: Elements of Number Theory. Springer-Verlag, 2003, ISBN 0-387-95587-9, S. 41–42.
[4]
James Joseph Tattersall: Elementary number theory in nine chapters. Cambridge University Press, 2005, ISBN 978-0-521-85014-8, S. 70–72.
[5]
Kenneth H. Rosen, Bart Goddard: Elementary Number Theory and Its Applications. 2000, ISBN 0-201-87073-8, S. 86–87.
[6]
Øystein Ore: Number Theory and Its History. McGraw–Hill, New York 1948, S. 247–248.
[7]
James Joseph Tattersall: Elementary number theory in nine chapters. Cambridge University Press, 2005, ISBN 978-0-521-85014-8, S. 72, 184–185.
[8]
Carl Friedrich Gauß: Theoria residuorum biquadraticorum.
[9]
John Stillwell: Elements of Number Theory. Springer-Verlag, 2003, ISBN 0-387-95587-9, S. 31–32.
[10]
Peter Gustav Lejeune Dirichlet & Richard Dedekind: Vorlesungen über Zahlentheorie. 2. Auflage. Friedrich Vieweg und Sohn, Braunschweig 1871, S. 30–31 (gdz.sub.uni-goettingen.de).
[11]
Peter Gustav Lejeune Dirichlet, Richard Dedekind: Vorlesungen über Zahlentheorie. 4. Auflage. Friedrich Vieweg und Sohn, Braunschweig 1894, Supplement XI.
[12]
siehe etwa: George Havas, Bohdan S. Majewski, Keith R. Matthews: Extended GCD algorithms (Memento vom 5. März 2014 im Internet Archive) (PDF; 160 kB). Technical Report TR0302, The University of Queensland, Brisbane 1994. oder G. Havas, B. S. Majewski, K. R. Matthews: Extended GCD and Hermite normal form algorithms via lattice basis reduction (Memento vom 5. März 2014 im Internet Archive) (PDF; 266 kB). Experimental Mathematics 7 (1998) No. 2, S. 125–136 und die reichhaltige Bibliografie darin
[13]
Eric W. Weisstein: Integer Relation. In: MathWorld (englisch).
[14]
Alan Meichsner: Integer relation algorithms and the recognition of numerical constants. Master's thesis, Simon Fraser University, Juni 2001.
[15]
George Szekeres: Multidimensional continued fractions. Ann. Univ. Sci. Budapest. Sectio Math. 13 (1970), S. 113–140
[16]
Helaman R. P. Ferguson, Rodney W. Forcade: Multidimensional Euclidean algorithms. J. Reine Angew. Math. 334 (1982) S. 171–181
[17]
Bettina Just: Generalizing the continued fraction algorithm to arbitrary dimensions. SIAM J. Comput. 21 (1992), S. 909–926
[18]
Carsten Rössner, Claus-Peter Schnorr: An optimal, stable continued fraction algorithm for arbitrary dimension. Electronic Colloquium on Computational Complexity, ECCC-TR96-020
Carsten Rössner, Claus-Peter Schnorr: An optimal, stable continued fraction algorithm. In: Lecture Notes Computer Science 1084, Springer 1996, S. 31–43
[19]
Jeffrey Lagarias: Geodesic multidimensional continued fractions. Proc. London Math. Soc. 69 (1994) S. 464–488
[20]
A. J. Cole, A. J. T. Davie: A game based on the Euclidean algorithm and a winning strategy for it. In: Mathematica Gazette. Band 53, 1969, S. 354–357, doi:10.2307/3612461.
[21]
E. L. Spitznagel: Properties of a game based on Euclid's algorithm. In: Mathematical Magazine. Band 46, 1973, S. 87–92.
[22]
Joe Roberts: Elementary Number Theory: A Problem Oriented Approach. MIT Press, Cambridge, MA 1977, ISBN 0-262-68028-9, S. 1–8.
[23]
Giovanni Cesari: Parallel implementation of Schönhage's integer GCD algorithm. In: ANTS-III (Lecture Notes Computer Science). Band 1423. Springer-Verlag, 1998, S. 64–76.
[24]
Andreas Klappenecker, Texas A&M University: Euclid’s Algorithm
[25]
Eric W. Weisstein: Lamé's Theorem. In: MathWorld (englisch).
[26]
Wissam Raji: Lame's Theorem
[27]
Keith Conrad: The Gaussian integers
[28]
University of California, Berkeley: Euclidean Algorithm II