Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler ${\displaystyle \operatorname {ggT} (a,b)}$ zweier natürlicher Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ noch zwei ganze Zahlen ${\displaystyle s}$ und ${\displaystyle t}$, die die folgende Gleichung erfüllen:

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

Der Algorithmus ist eine Erweiterung des bereits in der Antike bekannten euklidischen Algorithmus, der nur den größten gemeinsamen Teiler berechnet.

Das Haupteinsatzgebiet des erweiterten euklidischen Algorithmus ist die Berechnung der inversen Elemente in ganzzahligen Restklassenringen, denn wenn der Algorithmus das Tripel ${\displaystyle (d=\operatorname {ggT} (a,b),s,t)}$ ermittelt, ist entweder ${\displaystyle d=1}$ und damit ${\displaystyle 1\equiv t\cdot b{\pmod {a}}}$, ${\displaystyle t}$ also das multiplikative Inverse von ${\displaystyle b}$ modulo ${\displaystyle a,}$ oder aber ${\displaystyle d\neq 1,}$ was bedeutet, dass ${\displaystyle b}$ modulo ${\displaystyle a}$ kein Inverses hat. Dies ist die Grundlage für die Lösung von diophantischen Gleichungen oder allgemeiner von ganzzahligen linearen Gleichungssystemen. Ebenso ist die Bestimmung inverser Elemente eine Grundlage für den chinesischen Restsatz, welcher wiederum Grundlage des bedeutenden Tricks der kleinen Primzahlen in der berechenbaren Algebra ist. Dabei wird eine Aufgabe in mehreren endlichen Körpern gelöst und diese Teillösungen in immer größere Restklassenringe gehoben, bis sich eine ganzzahlige Lösung ablesen lässt. Der Algorithmus liefert zudem einen konstruktiven Beweis für das Lemma von Bézout, also ${\displaystyle 1=s\cdot a+t\cdot b}$.

Die am weitesten bekannte Version des euklidischen Algorithmus bezieht sich auf den Bereich der ganzen Zahlen. Jedoch kann er auf jeden Ring angewandt werden, in welchem eine Division mit kleinstem Rest durchgeführt werden kann. Solche Ringe werden euklidisch genannt, ein Beispiel ist der Polynomring in einer Variablen mit rationalen oder reellen Koeffizienten. In diesem kann immer ein eindeutig bestimmter Rest mit kleinstem Grad gefunden werden.

Funktionsweise der iterativen Variante

Die iterative Variante des EEA berechnet aus den vorgegebenen ${\displaystyle a,b}$ drei Zahlenfolgen ${\displaystyle r_{i},s_{i},t_{i}}$. Diese werden zunächst initialisiert:

${\displaystyle r_{0}=a,r_{1}=b}$

${\displaystyle s_{0}=1,s_{1}=0}$

${\displaystyle t_{0}=0,t_{1}=1}$

Dann wird für ${\displaystyle i=1,2,\ldots }$ berechnet:

${\displaystyle r_{i+1}=r_{i-1}-q_{i}\cdot r_{i}}$

${\displaystyle s_{i+1}=s_{i-1}-q_{i}\cdot s_{i}}$

${\displaystyle t_{i+1}=t_{i-1}-q_{i}\cdot t_{i}}$

Dabei ist ${\displaystyle q_{i}}$ der Quotient und ${\displaystyle r_{i+1}}$ der Rest der Division ${\displaystyle r_{i-1}:r_{i}}$.

Die Berechnung endet, sobald ${\displaystyle r_{i+1}=0}$ auftritt. Dann ist ${\displaystyle r_{i}}$ der ggT, und es gilt ${\displaystyle r_{i}=a\cdot s_{i}+b\cdot t_{i}}$.

Beispiel für die rekursive Variante

Zu der Vorgabe der Zahlen 99 und 78 produziert der einfache euklidische Algorithmus die Folge von Divisionen mit Rest:

${\displaystyle {\begin{matrix}{\underline {99}}&=&1\cdot {\underline {78}}+{\underline {21}}\\{\underline {78}}&=&3\cdot {\underline {21}}+{\underline {15}}\\{\underline {21}}&=&1\cdot {\underline {15}}+{\underline {\ 6}}\\{\underline {15}}&=&2\cdot {\underline {\ 6}}+{\underline {\ 3}}\\{\underline {6}}&=&2\cdot {\underline {\ 3}}+{\underline {\ 0}}\end{matrix}}}$

3 ist ein Teiler von 6 und damit der gesuchte größte gemeinsame Teiler von 99 und 78. Nun kann man diese Gleichungen rückwärts lesen und den Rest jeweils als Differenz der beiden anderen Terme darstellen. Setzt man diese Restdarstellungen rekursiv ineinander ein, so ergeben sich verschiedene Darstellungen des letzten Restes 3:

${\displaystyle {\begin{array}{rclcl}{\underline {\ 3}}&=&{\underline {15}}-2\cdot {\underline {\ 6}}\\&=&{\underline {15}}-2\cdot ({\underline {21}}-1\cdot {\underline {15}})&=&3\cdot {\underline {15}}-2\cdot {\underline {21}}\\&=&3\cdot ({\underline {78}}-3\cdot {\underline {21}})-2\cdot {\underline {21}}&=&3\cdot {\underline {78}}-11\cdot {\underline {21}}\\&=&3\cdot {\underline {78}}-11\cdot ({\underline {99}}-1\cdot {\underline {78}})&=&14\cdot {\underline {78}}-11\cdot {\underline {99}}\end{array}}}$

Der größte gemeinsame Teiler ist so als ganzzahlige Linearkombination der beiden Ausgangszahlen 78 und 99 dargestellt.

In der eben dargestellten Berechnungsvorschrift muss man erst den letzten Schritt des einfachen euklidischen Algorithmus abwarten, bevor die Berechnung der gesuchten Koeffizienten beginnen kann. Man kann aber auch ebenso alle anderen Reste als ganzzahlige Linearkombination von 78 und 99 darstellen und die zugehörigen Koeffizienten in jedem Schritt des einfachen euklidischen Algorithmus mit bestimmen:

${\displaystyle {\begin{array}{rclcrclcl}{\underline {99}}&=&1\cdot {\underline {78}}+{\underline {21}}&\iff &{\underline {21}}&=&&&1\cdot {\underline {99}}-1\cdot {\underline {78}}\\{\underline {78}}&=&3\cdot {\underline {21}}+{\underline {15}}&\iff &{\underline {15}}&=&1\cdot {\underline {78}}-3\cdot {\underline {21}}&=&-3\cdot {\underline {99}}+4\cdot {\underline {78}}\\{\underline {21}}&=&1\cdot {\underline {15}}+{\underline {\ 6}}&\iff &{\underline {\ 6}}&=&1\cdot {\underline {21}}-1\cdot {\underline {15}}&=&4\cdot {\underline {99}}-5\cdot {\underline {78}}\\{\underline {15}}&=&2\cdot {\underline {\ 6}}+{\underline {\ 3}}&\iff &{\underline {\ 3}}&=&1\cdot {\underline {15}}-2\cdot {\underline {\ 6}}&=&-11\cdot {\underline {99}}+14\cdot {\underline {78}}\end{array}}}$

Tabellarische Darstellung

Allgemeine mathematische Grundlage

Der euklidische Algorithmus erzeugt zu vorgegebenen ganzen Zahlen a und b (allgemein: Elementen eines euklidischen Rings) zwei Folgen: eine Folge ${\displaystyle (q_{k})_{k}}$ von Quotienten und eine Folge ${\displaystyle (r_{k})_{k}}$ von Resten, wobei ${\displaystyle r_{0}=a,\;r_{1}=b}$. In jedem Schritt ${\displaystyle k=1,2,\ldots }$ gilt dabei

${\displaystyle r_{k-1}=q_{k}\cdot r_{k}+r_{k+1}}$, ${\displaystyle |r_{k+1}|<|r_{k}|}$.

Nach endlich vielen Schritten ergibt sich der Rest Null.

Wir gehen nun zu Restklassen modulo b über. Es ist trivial zu sehen, dass ${\displaystyle r_{0}=a=1\cdot a}$ und ${\displaystyle r_{1}=b=0\cdot a+1\cdot b}$ Vielfache von ${\displaystyle a}$ nach Hinzufügen oder Abziehen von Vielfachen von ${\displaystyle b}$ sind. Genauer sind die Restklassen ${\displaystyle [r_{k}]_{b}}$ Vielfache der Restklasse ${\displaystyle [a]_{b}}$ für ${\displaystyle k=0,1}$, und nach Rekursionsvorschrift auch für ${\displaystyle k=2,3,\ldots }$. Es kann also eine Folge von Multiplikatoren ${\displaystyle (s_{k})_{k}}$ konstruiert werden, die mit ${\displaystyle s_{0}=1}$ und ${\displaystyle s_{1}=0}$ initialisiert ist, so dass

${\displaystyle r_{k}\equiv s_{k}\cdot a{\pmod {b}}}$

gilt. Es ergibt sich die rekursive Beziehung

${\displaystyle s_{k-1}\equiv q_{k}\cdot s_{k}+s_{k+1}}$.

Man kann diese Rekursion in folgende Abfolge von Schritten für den erweiterten euklidischen Algorithmus fassen:

• Erhalte ${\displaystyle a}$ und ${\displaystyle b}$ als Eingabe.
• Setze ${\displaystyle k=0}$, ${\displaystyle r_{0}=a,\;r_{1}=b}$, ${\displaystyle s_{0}=1}$ und ${\displaystyle s_{1}=0}$.
• Wiederhole:
  • Erhöhe ${\displaystyle k}$ um eins.
  • Bestimme den ganzzahligen Quotienten ${\displaystyle q_{k}=r_{k-1}\;\div \;r_{k}}$.
  • Setze ${\displaystyle r_{k+1}=r_{k-1}-q_{k}\cdot r_{k}}$ und ${\displaystyle s_{k+1}=s_{k-1}-q_{k}\cdot s_{k}}$.
• bis ${\displaystyle r_{k+1}=0}$ gilt.
• Gib den Rest ${\displaystyle r_{k}=\operatorname {ggT} (a,b)}$ und die Zahl ${\displaystyle s_{k}}$ mit ${\displaystyle \operatorname {ggT} (a,b)\equiv s_{k}\cdot a{\pmod {b}}}$ zurück.

Jeder Schritt enthält implizit auch einen Multiplikator ${\displaystyle t_{k}=(r_{k}-s_{k}\cdot a)\div b}$, wobei diese Division keinen Rest lässt. Die Folge ${\displaystyle (t_{k})_{k}}$ kann auch explizit bestimmt werden, es gelten ${\displaystyle t_{0}=0}$, ${\displaystyle t_{1}=1}$ und

${\displaystyle t_{k-1}\equiv q_{k}\cdot t_{k}+t_{k+1}}$.

Nach dem letzten Schritt ergibt sich nun ${\displaystyle \operatorname {ggT} (a,b)=s_{k}\cdot a+t_{k}\cdot b}$

Der Übersicht halber werden beim händischen Rechnen auch noch die Hilfsfolgen ${\displaystyle (a_{k}=r_{k-1})_{k}}$ und ${\displaystyle (b_{k}=r_{k})_{k}}$ sowie ${\displaystyle (u_{k}=s_{k-1})_{k}}$ sowie ${\displaystyle (v_{k}=t_{k-1})_{k}}$ mitgeführt.

Algorithmus

a,b: zwei Zahlen für die der erweiterte euklidische Algorithmus durchgeführt wird

extended_euclid(a,b)
1  wenn b = 0
2      dann return (a,1,0)
3  (d',s',t') ${\displaystyle \leftarrow }$ extended_euclid(b, a mod b)
4  (d,s,t) ${\displaystyle \leftarrow }$ (d',t',s' – (a div b)t')
5  return (d,s,t)

#include <iostream>
using namespace std;

int gcdExtendedRecursive(int a, int b, int* s, int* t)
{
    if (b == 0)
    {
        *s = 1;
        *t = 0;
        return a;
    }
    int s1, t1; // Deklaration der Variablen, die die Ergebnisse des rekursiven Aufrufs speichern
    int d = gcdExtendedRecursive(b, a % b, &s1, &t1); // Rekursiver Aufruf der Methode
    *s = t1;
    *t = s1 - (a / b) * t1;
    return d;
}

int gcdExtendedIterative(int a, int b, int* s, int* t)
{
    *s = 1; // Initialisierung der Zeiger
    *t = 0;
    int u = 0; // Deklaration der lokalen Variablen
    int v = 1;
    while (b != 0)
    {
        int q = a / b;
        int b1 = b; // Variable zum Zwischenspeichern
        b = a - q * b;
        a = b1;
        int u1 = u; // Variable zum Zwischenspeichern
        u = *s - q * u;
        *s = u1;
        int v1 = v; // Variable zum Zwischenspeichern
        v = *t - q * v;
        *t = v1;
    }
    return a;
}

// Hauptfunktion die das Programm ausführt
int main()
{
    int a, b, s, t; // 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
    int d = gcdExtendedRecursive(a, b, &s, &t); // Aufruf der rekursiven Funktion
    cout << "Groesster gemeinsamer Teiler: " << s << " * " << a << " + " << t << " * " << b << " = " << d << endl; // Ausgabe auf der Konsole
    d = gcdExtendedIterative(a, b, &s, &t); // Aufruf der iterativen Funktion
    cout << "Groesster gemeinsamer Teiler: " << s << " * " << a << " + " << t << " * " << b << " = " << d << endl; // Ausgabe auf der Konsole
}

Hinweise zur effizienten Computerimplementierung

Siehe auch

• Euklidischer Algorithmus
• Steinscher Algorithmus

Weblinks

• Universität Ulm: "Elementare Zahlentheorie"
• Iterative Variante in Java (Quellcode)
• JavaScript-Rechner mit Berechnungsdetails und Zwischenschritten
• Alternative Darstellung der Berechnung
• Video: Erweiterter Euklidischer Algorithmus Teil 1. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19885.
• Video: Erweiterter Euklidischer Algorithmus Teil 2. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19886.
• Video: Erweiterter Euklidischer Algorithmus Teil 3. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19887.
• Hochschule Flensburg: Erweiterter euklidischer Algorithmus
• GeeksforGeeks: Euclidean algorithms (Basic and Extended)

Einzelnachweise

1. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7.