Der euklidische Algorithmus

2.3. Der euklidische Algorithmus#

Kennt man die Primfaktorzerlegung der natürlichen Zahlen \(a\) und \(b\), so kann man deren größten gemeinsamen Teiler \(\ggT(a,b)\) direkt berechnen, wie wir in Definition 2.10 gesehen haben. Es gibt aber auch einen anderen Weg, der ohne Primfaktorzerlegungen auskommt.

Sind \(a,b,q,r\in\Z\) ganze Zahlen für die gilt \(a=qb+r\), so können wir nämlich für eine beliebige ganze Zahl \(d\in\Z\) folgenden Zusammenhang folgern:

\[d\in\mathrm{gT}(a,b) \ \iff \ d|a \wedge d|b \ \iff \ d|a \wedge d|b \wedge d|r \ \iff \ d|b \wedge d|r \ \iff \ d\in\mathrm{gT}(b,r).\]

Da dies für alle ganzen Teiler \(d\in \mathrm{gT}(a,b)\) gilt erkennen wir, dass \(gT(a,b)=gT(b,r)\) und damit auch automatisch auch

(2.3)#\[\ggT(a,b)=\ggT(b,r).\]

Diese Beobachtung motiviert den euklidischen Algorithmus, welcher im Folgenden beschrieben wird:

Algorithmus 2.2 (Euklidischer Algorithmus (Variante I))

Seien zwei natürliche Zahlen \(a,b\in\N_0\) gegeben. Rekursiv wird nun eine natürliche Zahlenfolge \(a_i\in\N_0\) definiert, wobei man die Folge mit \(a_0=a\) und \(a_1=b\) beginnt. Sind für einen Index \(i\ge 0\) die Zahlen \(a_i\) und \(a_{i+1}\) bereits definiert, so unterscheidet man:

  • Ist \(a_{i+1}=0\), so bricht man den Algorithmus ab. Hierbei nehmen wir an, dass \(n\) der kleinste Index mit der Eigenschaft \(a_{n+1}=0\) ist. Es ist dann \(\ggT(a,b)=a_i\).

  • Ist jedoch \(a_{i+1}>0\), so dividiert man die natürliche Zahl \(a_i\) durch \(a_{i+1}\) und erhält somit den Quotienten \(q_i\) und den Rest \(a_{i+2} := r_i = a_i\bmod a_{i+1}\). Es ist klar, dass dadurch die natürliche Zahlenfolge streng monoton fällt und es gilt \(0\le a_{i+2}<a_{i+1}\).

Explizit ergibt sich das Schema (im Fall \(a_1>0\)):

\[\begin{aligned} a_0&=&q_0a_1+a_2\quad\text{ mit }\quad 0

Nach Terminieren des Algorithmus hat man schließlich den größten gemeinsamen Teiler von \(a = a_0\) und \(b=a_1\) bestimmt durch

\[\ggT(a,b)=a_n.\]

Die Zahl \(n \in \N\) bezeichnen wir auch als Schrittzahl des euklidischen Algorithmus für die gegebenen natürlichen Zahlen \(a,b\in\N_0\).

Das der euklidische Algorithmus in der Tat den größten gemeinsamen Teiler berechnet ergibt sich durch rekursive Anwendung der Beobachtung in (2.3), denn aus \(a_i=q_ia_{i+1}+a_{i+2}\) folgt mit der Vorbemerkung \(\ggT(a_i,a_{i+1})=\ggT(a_{i+1},a_{i+2})\) und damit

\[\ggT(a_0,a_1)=\ggT(a_1,a_2)=\dots=\ggT(a_{n-1},a_n)=\ggT(a_n,0)=a_n.\]

Wir haben mit Algorithmus 2.2 eine Möglichkeit gefunden, den \(\ggT(m,n)\) zu berechnen ohne explizit die Primfaktorzerlegung von \(m\) und \(n\) zu kennen. Da es für Letztere keinen bekannten effizienten Algorithmus gibt ist der euklidische Algorithmus ein wichtiges Werkzeug in der Zahlentheorie.

Wir illustrieren das Prinzip und die benötigten Rechenschritte des euklidischen Algorithmus an Hand einiger Beispiele.

Beispiel 2.12 (Eukldischer Algorithmus (Variante I))

Wir berechnen den größten gemeinsamen Teiler im Folgenden in einigen Beispielen mit immer größer werdenden natürlichen Zahlen.

  1. Wir wollen zunächst \(\ggT(12345,987)\) berechnen:

    \[\begin{aligned} 12345&=& 12\cdot 987+501,\\ 987&=&1\cdot 501+486,\\ 501&=&1\cdot 486+15,\\ 486&=&32\cdot 15+6,\\ 15&=&2\cdot 6+3,\\ 6&=&2\cdot 3+0. \end{aligned}\]

    Es gilt also \(\ggT(12345,987)=3\), was wir nach 6 Divisionen mit Rest herausgefunden haben. Zum Vergleich betrachten wir die jeweiligen Primfaktorzerlegungen mit \(12345=3\cdot 5\cdot 823\) und \(987=3\cdot 7\cdot 47\).

  2. Nun berechnen wir \(\ggT(9264857236,2453245253)\). Mit insgesamt 23 Divisonen ergibt sich

    \[\begin{aligned} 9264857236 &=& 3 \cdot 2453245253 + 1905121477\\ 2453245253 &=& 1 \cdot 1905121477 + 548123776\\ 1905121477 &=& 3 \cdot 548123776 + 260750149\\ 548123776 &=& 2 \cdot 260750149 + 26623478\\ 260750149 &=& 9 \cdot 26623478 + 21138847\\ 26623478 &=& 1 \cdot 21138847 + 5484631\\ 21138847 &=& 3 \cdot 5484631 + 4684954\\ 5484631 &=& 1 \cdot 4684954 + 799677\\ 4684954 &=& 5 \cdot 799677 + 686569\\ 799677 &=& 1 \cdot 686569 + 113108\\ 686569 &=& 6 \cdot 113108 + 7921\\ 113108 &=& 14 \cdot 7921 + 2214\\ 7921 &=& 3 \cdot 2214 + 1279\\ 2214 &=& 1 \cdot 1279 + 935\\ 1279 &=& 1 \cdot 935 + 344\\ 935 &=& 2 \cdot 344 + 247\\ 344 &=& 1 \cdot 247 + 97\\ 247 &=& 2 \cdot 97 + 53\\ 97 &=& 1 \cdot 53 + 44\\ 53 &=& 1 \cdot 44 + 9\\ 44 &=& 4 \cdot 9 + 8\\ 9 &=& 1 \cdot 8 + 1\\ 8 &=& 8 \cdot 1 + 0 \end{aligned}\]

    Also ist der größte gemeinsame Teiler der beiden Zahlen 1.

  3. Für die 20-stelligen Zahlen 15847523452462634165 und 87648572364875263842 erhält man den größten gemeinsamen Teiler nach 40 Divisionen mit Rest als

    \[\ggT(15847523452462634165,87648572364875263842)=1\]

    Die Zahlen sind also teilerfremd. Hierzu haben wir berechnet:

    \[\begin{aligned} 15847523452462634165 &=& 0 \cdot 87648572364875263842 + 15847523452462634165\\ 87648572364875263842 &=& 5 \cdot 15847523452462634165 + 8410955102562093017\\ 15847523452462634165 &=& 1 \cdot 8410955102562093017 + 7436568349900541148\\ 8410955102562093017 &=& 1 \cdot 7436568349900541148 + 974386752661551869\\ 7436568349900541148 &=& 7 \cdot 974386752661551869 + 615861081269678065\\ 974386752661551869 &=& 1 \cdot 615861081269678065 + 358525671391873804\\ 615861081269678065 &=& 1 \cdot 358525671391873804 + 257335409877804261\\ 358525671391873804 &=& 1 \cdot 257335409877804261 + 101190261514069543\\ 257335409877804261 &=& 2 \cdot 101190261514069543 + 54954886849665175\\ 101190261514069543 &=& 1 \cdot 54954886849665175 + 46235374664404368\\ 54954886849665175 &=& 1 \cdot 46235374664404368 + 8719512185260807\\ 46235374664404368 &=& 5 \cdot 8719512185260807 + 2637813738100333\\ 8719512185260807 &=& 3 \cdot 2637813738100333 + 806070970959808\\ 2637813738100333 &=& 3 \cdot 806070970959808 + 219600825220909\\ 806070970959808 &=& 3 \cdot 219600825220909 + 147268495297081\\ 219600825220909 &=& 1 \cdot 147268495297081 + 72332329923828\\ 147268495297081 &=& 2 \cdot 72332329923828 + 2603835449425\\ 72332329923828 &=& 27 \cdot 2603835449425 + 2028772789353\\ 2603835449425 &=& 1 \cdot 2028772789353 + 575062660072\\ 2028772789353 &=& 3 \cdot 575062660072 + 303584809137\\ 575062660072 &=& 1 \cdot 303584809137 + 271477850935\\ 303584809137 &=& 1 \cdot 271477850935 + 32106958202\\ 271477850935 &=& 8 \cdot 32106958202 + 14622185319\\ 32106958202 &=& 2 \cdot 14622185319 + 2862587564\\ 14622185319 &=& 5 \cdot 2862587564 + 309247499\\ 2862587564 &=& 9 \cdot 309247499 + 79360073\\ 309247499 &=& 3 \cdot 79360073 + 71167280\\ 79360073 &=& 1 \cdot 71167280 + 8192793\\ 71167280 &=& 8 \cdot 8192793 + 5624936\\ 8192793 &=& 1 \cdot 5624936 + 2567857\\ 5624936 &=& 2 \cdot 2567857 + 489222\\ 2567857 &=& 5 \cdot 489222 + 121747\\ 489222 &=& 4 \cdot 121747 + 2234\\ 121747 &=& 54 \cdot 2234 + 1111\\ 2234 &=& 2 \cdot 1111 + 12\\ 1111 &=& 92 \cdot 12 + 7\\ 12 &=& 1 \cdot 7 + 5\\ 7 &=& 1 \cdot 5 + 2\\ 5 &=& 2 \cdot 2 + 1\\ 2 &=& 2 \cdot 1 + 0 \end{aligned}\]

  4. Mit dem euklidischen Algorithmus erhalten wir in 79 Schritten

    \[\ggT(17^{60}+20882693916,13^{40}+14609017703)=25937424629.\]

  5. Für die (zufällig gewählten) 1000-stelligen Zahlen

    \[a=71^{540}+92600321179110855935\quad\text{ und }\quad b=83^{521}+75133748210326629851\]

    erhält man mit dem euklidischen Algorithmus nach 1978 Schritten \(\ggT(a,b)=2\).

Wie das obige Beispiel zeigen soll wächst die Anzahl der benötigten Rechenschritte im euklidischen Algorithmus viel langsamer im Vergleich zu der wachsenden Stellenzahl der untersuchten Zahlen.

Der größte gemeinsame Teiler lässt sich mit dem euklidischen Algorithmus also sehr schnell berechnen. Daher wird dieser Algorithmus in der Praxis auch oft eingesetzt. Für die Berechnung des größten gemeinsamen Teiler braucht man im euklidischen Algorithmus die Quotienten eigentlich \(q_i\) nicht, sofern man \(a_{i}\bmod a_{i+1}\) anders als durch \(a_i-\floor{\frac{a_i}{a_{i+1}}}a_{i+1}\) berechnen kann. Berücksichtigt man dies erhält man die folgende Variante.

Algorithmus 2.3 (Euklidischer Algorithmus (Variante II))

Seien zwei natürliche Zahlen \(a,b\in\N_0\) gegeben. Rekursiv wird nun eine natürliche Zahlenfolge \(a_i\in\N_0\) definiert, wobei man die Folge mit \(a_0=a\) und \(a_1=b\) beginnt. Sind für einen Index \(i\ge 0\) die Zahlen \(a_i\) und \(a_{i+1}\) bereits definiert, so unterscheidet man:

  • Ist \(a_{i+1}=0\), so bricht man den Algorithmus ab. Es ist dann \(\ggT(a,b)=a_i\).

  • Ist jedoch \(a_{i+1}>0\), so definiert man direkt \(a_{i+2}=a_i\bmod a_{i+1}\).

Explizit erhalten wir also die Folge der natürlichen Zahlen \((a_i) \subset \N_0\) als:

\[a_0,\ a_1, \ a_2=a_0\bmod a_1,\ a_3=a_1\bmod a_2,\ a_4=a_2\bmod a_3,\ \dots\quad a_{n+1}=a_{n-1}\bmod a_n=0,\]

Nach Terminieren des Algorithmus hat man schließlich den größten gemeinsamen Teiler von \(a = a_0\) und \(b=a_1\) bestimmt durch

\[\ggT(a,b)=a_n.\]

Wir illustrieren in folgendem Beispiel kurz den Unterschied in der Angabe der Zahlenfolge bei dieser Variante des euklidischen Algorithmus.

Beispiel 2.13 (Euklidischer Algorithmus (Variante II))

Wir wollen zunächst für die beiden natürlichen Zahlen \(a=12345\) und \(b=987\) mit \(a>b\) den größten gemeinsamen Teiler mit Algorithmus 2.3 bestimmen. Ohne die Berücksichtigung der Quotienten \(q_i\) liefert dies die folgende Zahlenfolge \(a_i\):

\[12345,\quad 987,\quad 501,\quad 486,\quad 15,\quad 6,\quad 3,\quad 0.\]

Startet man mit umgekehrten Definitionen \(a=987\) und \(b=12345\), so erhält man hingegen die um einen Schritt verlängerte Zahlenfolge \(a_i\):

\[987,\quad 12345,\quad 987,\quad 501,\quad 486,\quad 15,\quad 6,\quad 3,\quad 0.\]

In Python lässt sich Algorithmus 2.3 sehr kompakt implementieren als:

def ggT_v2(a,b): 
  a=[a,b]
  while a[-1]>0:
    a.append(a[-2]%a[-1])
  return a[-2]

Verwendet man hingegen zwei Zahlenfolgen, so lässt sich der euklidische Algorithmus noch etwas einfacher angeben.

Algorithmus 2.4 (Euklidischer Algorithmus (Variante III))

Seien zwei natürliche Zahlen \(a,b\in\N_0\) gegeben. Rekursiv werden nun zwei natürliche Zahlenfolgen \(b_i, a_i\in\N_0\) definiert, wobei man die Folge mit \(a_0=a\) und \(b_0=b\) beginnt. Sind für einen Index \(i\ge 0\) die Zahlen \(a_i\) und \(b_i\) bereits definiert, so unterscheidet man:

  • Ist \(b_i=0\), so bricht man ab. Dann gilt \(\ggT(a,b)=a_i\).

  • Ist jedoch \(b_i>0\), so definiert man \(a_{i+1}=b_i\) und \(b_{i+1}=a_i\bmod b_i\).

Mit dieser Variante lässt sich der euklidische Algorithmus noch etwas eleganter in Python implementieren als

def ggT_v3(a,b): 
  while b>0:
    a,b=b,a%b
  return a

Man kann recht gut abschätzen, welchen Rechenaufwand der euklidische Algorithmus besitzt. Um dies zu verstehen benötigen wir zunächst noch ein paar Aussagen über die Fibonacci-Zahlen.

2.3.1. Fibonacci-Zahlen#

Definition 2.14 (Fibonacci-Folge)

Die Folge der Fibonacci-Zahlen \((f_n)_{n\ge 0}\) wird rekursiv durch folgende Differenzengleichung definiert

\[f_0=0,\quad f_1=1\quad\text{ und }\quad f_n=f_{n-1}+f_{n-2}\text{ für }n\ge 2\]

definiert. Die resultierende Folge ist also

\[0,\quad 1,\quad 1,\quad 2,\quad 3,\quad 5,\quad 8,\quad 13,\quad 21, \quad 34,\quad 55,\quad 89,\quad 144,\quad 233,\quad 377,\quad \dots\]

Die folgende Python-Funktion berechnet iterativ eine Liste mit den ersten \(n\) Fibonacci-Zahlen:

def fibonacci_liste(n):
  f=[0,1]
  while len(f)<n:
    f.append(f[-1]+f[-2])
  return f

Das folgende Lemma gibt eine explizite Berechnungsformel für das \(n\)-te Folgenglied \(f_n\) der Fibonacci-Folge an und liefert uns so eine Abschätzung für das Wachstumsverhalten, die später für die Analyse des euklidischen Algorithmus benötigt wird.

Lemma 2.6 (Explizite Formel für Fibonacci-Zahlen)

Für die Fibonacci-Folge gelten folgende zwei Aussagen:

  1. Das \(n\)-te Glied der Fibonacci-Folge \(f_n, n \ge 0\) lässt sich explizit berechnen als

    \[f_n \ = \ \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n- (\frac{1-\sqrt{5}}{2})^n].\]

  2. Das Wachstum der Fibonacci-Folge ist nach unten beschränkt durch

    \[n \ \le \ 4.785 \cdot \log_{10}f_{n+2}.\]

Proof. Wie beweisen die beiden Aussagen separat.

  1. Man kann die explizite Gestalt generell durch vollständige Induktion beweisen. Wir geben hier aber einen Ansatz an, der konstruktiv ist und erklärt woher genau die explizite Formel kommt.
    Sei \(\alpha \ne 0\) eine reelle Zahl. Wir fragen uns zunächst wann die Zahl \(g_n := \alpha^n\) die Rekursionsformel \(g_n=g_{n-1}+g_{n-2}\) erfüllt. Betrachten wir den Fall \(n=2\), so sehen wir ein, dass dies genau dann der Fall ist, wenn \(\alpha^2=\alpha+1\) gilt. Mit Hilfe der Mitternachtsformel wissen wir also, dass \(\alpha=\frac{1\pm\sqrt{5}}{2}\) gelten muss.

    Wir setzen also für die beiden Lösungen

    \[\alpha := \frac{1+\sqrt{5}}{2},\quad \beta := \frac{1-\sqrt{5}}{2}.\]

    Für beliebige reelle Zahlen \(x,y \in \R\) erfüllt dann auch

    \[h_n=x\alpha^n+y\beta^n\]

    die Rekursionsformel \(h_n=h_{n-1}+h_{n-2}\), da

    \[h_n = x\alpha^n+y\beta^n = x(\alpha^{n-1} + \alpha^{n-2}) + y(\beta^{n-1} + \beta^{n-2}) = \underbrace{x\alpha^{n-1} + y\beta^{n-1}}_{=h_{n-1}} + \underbrace{x\alpha^{n-2} + y\beta^{n-2}}_{=h_{n-2}}.\]

    Nun ist also

    \[h_0= x\alpha^0 + y\beta^0 = x+y \quad \text{ und } \quad h_1= x\alpha^1 +y \beta^1 = x\frac{1+\sqrt{5}}{2} + y\frac{1-\sqrt{5}}{2} = (x+y)\frac{1}{2}+(x-y)\frac{\sqrt{5}}{2}.\]

    Da die Rekursionsformel für alle \(x,y \in \R\) gilt, können wir \(y:=-x\) wählen. In dem Fall wird \(h_0=0\) und \(h_1=x\sqrt{5}\). Wählen wir dann weiter \(x:=\frac{1}{\sqrt{5}}\), so wird auch noch \(h_1=1\).

    Aus \(h_0 = 0 = f_0\), \(h_1 = 1 = f_1\) und der gleichen Rekursionsformel \(f_n = f_{n-1} + f_{n-2}\) folgt nun sofort \(f_n=h_n\) für alle \(n\ge 0\). Damit gilt auch schon die Behauptung

    \[f_n = h_n = x\alpha^n + y \beta^n = \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2}\right)^n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right].\]

  2. Die obige explizite Formel für \(f_n\) liefert

    \[\begin{aligned} \quad\quad\quad\quad f_{n+2}&=&\frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n+2}- \left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right]\\ %TODO Warum gilt das? &=& \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} \left[1-\left(\frac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n+2}\right] \\ &=& \left(\frac{1+\sqrt{5}}{2}\right)^n \cdot \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^2 \left[1-\left(\frac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n+2}\right] \\ &=& \left(\frac{1+\sqrt{5}}{2}\right)^n \cdot \frac{5+3\sqrt{5}}{10} \left[1-(-1)^n \left(\frac{3-\sqrt{5}}{2}\right)^{n+2}\right], \end{aligned}\]

    so dass folgt

    \[\begin{aligned} \quad\quad\quad f_{n+2} \ \ge \ \left(\frac{1+\sqrt{5}}{2}\right)^n &\iff& \frac{5+3\sqrt{5}}{10}\left[1-(-1)^n \left(\frac{3-\sqrt{5}}{2}\right)^{n+2}\right] \ \ge \ 1 \\ &\iff& 1-(-1)^n \left(\frac{3-\sqrt{5}}{2}\right)^{n+2} \ \ge \ \frac{-5+3\sqrt{5}}{2} \\ &\iff& \frac{7-3\sqrt{5}}{2} \ \ge \ (-1)^n \left(\frac{3-\sqrt{5}}{2}\right)^{n+2} \\ &\hphantom{\iff}& = \ (-1)^n \left(\frac{3-\sqrt{5}}{2}\right)^n \cdot \frac{7-3\sqrt{5}}{2}\\ &\iff& 1 \ \ge \ (-1)^n \left(\frac{3-\sqrt{5}}{2}\right)^n \ \approx \ (-1)^n \cdot 0.38^n. \end{aligned}\]

    Die letzte Ungleichung ist für \(n\ge 0\) richtig, d.h. es gilt

    \[f_{n+2} \ \ge \ \left(\frac{1+\sqrt{5}}{2}\right)^n.\]

    Die liefert uns sofort

    \[n \ \le \ \frac{1}{\log_{10} \frac{1+\sqrt{5}}{2}} \log_{10}f_{n+2} \ \le \ 4.785 \cdot \log_{10}f_{n+2}.\]

◻

Folgendes Beispiel zeigt den Nutzen der gerade bewiesenen Aussagen über die Fibonacci-Folge.

Beispiel 2.14 (Wachstum der Fibonacci-Folge)

Die folgenden Beispielzahlen zeigen die Qualität der Abschätzung von Lemma 2.6:

\(n\)

0

1

2

3

4

5

6

10

1000

1001

\(4.785\log_{10}f_{n+2}\)

0

1.44

2.28

3.34

4.32

5.33

6.33

10.33

1000.33

1001.33

Mit der expliziten Formel für das \(n\)-te Glied der Fibonacci Folge findet man außerdem heraus, dass

\[f_{480}\approx 0.92\cdot 10^{100},\quad f_{479}\approx 0.57\cdot 10^{100},\]

d.h. \(f_{479}\) und \(f_{480}\) sind 100-stellige Dezimalzahlen.

2.3.2. Rechenaufwand#

Wir wenden jetzt die Aussagen über Fibonacci-Zahlen an um folgenden Satz zu beweisen:

Satz 2.4 (Rechenaufwand des euklidischen Algorithmus)

Um den größten gemeinsamen Teiler zweier natürlicher Zahl \(a,b \in \N\) mit \(a>b\) zu berechnen, braucht man mit dem euklidischen Algorithmus weniger als \(4.785 \cdot \log_{10}a\) Divisionen mit Rest.

Proof. Nehmen wir an die Schrittzahl zur Berechnung des größten gemeinsamen Teilers von \(a\) und \(b\) sei \(n \in \N\). Wir definieren dann \(g_{n+1}=a\) und \(g_n=b\). Aus Algorithmus 2.2 ergibt sich dann:

\[\begin{split} g_{n+1}=&q_{n+1}g_{n}+g_{n-1},\quad 1 \le g_{n-1}

Wir wollen nun die Folgeglieder der \(g_i\) mit der Fibonacci-Folge \(f_0=0\), \(f_1=1\), \(f_2=1\), \(f_3=2, \ldots, f_i=f_{i-1}+f_{i-2}\) vergleichen.

Wir zeigen zunächst durch Induktion, dass für \(i\ge 1\) gilt \(g_i\ge f_{i+1}\).
Induktionsanfang: Für \(i=1\) ist \(g_1=\ggT(a,b)\ge 1=f_2\). Für \(i=2\) gilt \(g_2>g_1\ge 1\), also \(g_2\ge 2=f_3\).
Induktionsschritt: Wir vollziehen nun den Induktionsschluss für \(i\ge 3\), wobei wir \(q_i\ge 1\) benutzen:

\[g_i=q_ig_{i-1}+g_{i-2}\ge g_{i-1}+g_{i-2}\ge f_i+f_{i-1}=f_{i+1},\]

womit \(g_i\ge f_{i+1}\) für \(i\ge 1\) durch Induktion bewiesen wäre.

Es folgt:

\[a=g_{n+1}\ge f_{n+2}\]

und daher mit obigem Lemma

\[n \ \le \ 4.785 \cdot \log_{10}f_{n+2}\le 4.785 \cdot \log_{10}a,\]

was die Behauptung zeigt. ◻

Die effiziente Berechnung des größten gemeinsamen Teilers mit dem euklidischen Algorithmus hat auch für die Faktorisierung von großen Zahlen eine Bedeutung. Die Maple-Funktion ifactor beispielsweise beginnt den Faktorisierungsversuch einer natürlichen Zahl \(n\in\N\) mit folgenden Schritten:

  1. Zunächst wird immer wieder \(\ggT(n,720720)\) (mit \(720720=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\)) gebildet und aus \(n\) herausdividiert, bis \(\ggT(n,720720)=1\) ist. Damit erhält man schließlich die Zerlegung

    \[n=2^{e_1}\cdot 3^{e_2}\cdot 5^{e_3}\cdot 7^{e_4}\cdot 11^{e_5}\cdot 13^{e_6}\cdot n',\]

    wobei der Faktor \(n'\in\N\) von keiner der Primzahlen 2, 3, 5, 7, 11, 13 mehr geteilt wird.

  2. Im nächsten Schritt bildet man

    \[d \ := \ 17\cdot 19\cdot \dots\cdot 1699=p_7\cdot p_8\cdot \dots p_{266}\]

    das Produkt der 260 Primzahlen zwischen 17 und 1699 (\(d\) hat 718 Dezimalstellen). Nun wird solange \(\ggT(n',d)\) gebildet und aus \(n'\) herausdividiert, bis \(\ggT(n',d)=1\) ist. Man erhält dann die Zerlegung

    \[n=2^{e_1}\cdot 3^{e_2}\cdot \ldots \cdot 17^{e_7} \cdot \ldots \cdot 1699^{e_{266}}\cdot n'',\]

    wobei der Faktor \(n''\in\N\) nun keinen Primteiler \(<1700\) mehr hat.

  3. Nun erst werden andere Faktorisierungsmethoden eingesetzt.

Erfahrungsgemäß funktioniert das obige Faktorisierungsverfahren mit der Bildung der größten gemeinsamen Teiler schneller als wenn man direkt versucht, alle kleinen Primteiler zwischen 2 und 1699 einzeln herauszuteilen.

2.3.3. Lineare diophantische Gleichungen#

Lineare diophantische Gleichungen sind ein Spezialfall von diophantischen Gleichungen (benannt nach dem griechischen Mathematik Diophantos von Alexandria), die unter Anderem in der algebraischen Zahlentheorie untersucht werden. Es handelt sich hierbei um lineare Gleichungen mit drei gegebenen Koeffizienten \(a,b,c \in \Z\) für die zwei ganzzahlige Lösungen \(x,y \in \Z\) gesucht werden und die von der folgenden Form sind

\[c \ = \ ax + by.\]

Solche Gleichungen tauchen in spezieller Form auch im Alltag auf, wie zum Beispiel bei der Aufgabe den Betrag von 34€ mit Hilfe von 5€-Scheinen und 2€-Münzen zu bezahlen. Die resultierende Gleichung lautet

\[34 \ = \ 5x + 2y.\]

Nimmt man nur natürliche Zahlen \(x,y\in\N_0\) als mögliche Lösungen an, so existieren nur 4 unterschiedliche Lösungen, nämlich:

\[(x_1,y_1) = (6,2), \quad (x_2,y_2) = (4,7), \quad (x_3,y_3) = (2,12), \quad (x_4,y_4) = (0, 17).\]

Der folgende Satz untersucht einen Spezialfall von linearen diophantischen Gleichungen für die die Existenz von Lösungen garantiert werden kann.

Satz 2.5 (Lemma von Bézout)

Für alle ganzzahligen Koeffizienten \(a,b\in\Z\) existiert eine Lösung \(x,y\in\Z\), so dass die folgende lineare diophantische Gleichung erfüllt ist:

\[\ggT(a,b) \ = \ xa+yb,\]

d.h., der größte gemeinsame Teiler von \(a\) und \(b\) lässt sich als eine Linearkombination der beiden Zahlen mit ganzzahligen Koeffizienten darstellen.

Proof. Wir skizzieren im Folgenden einen konstruktiven Beweis der Aussage mit Hilfe des euklidischen Algorithmus.

Wenden wir zunächst den euklidischen Algorithmus auf \(a=a_0\) und \(b=a_1\) an, so erhalten wir das folgende Schema:

\[\begin{aligned} a_0 &=& q_0a_1+a_2\quad\text{ mit }\quad 0

Dann ist bekanntermaßen \(a_n=\ggT(a,b)\).

Wir können nun beginnend mit der vorletzten Zeile des obigen Schemas die Restdarstellungen der Divisoren rückwärts einsetzen, d.h., wir erhalten:

\[a_n = a_{n-2} - q_{n-2}a_{n-1} = a_{n-2} - q_{n-2}(a_{n-3} - q_{n-3}a_{n-2}) = \ldots\]

Schließlich lässt sich die Zahl \(a_n\) als Linearkombination von \(a_0\) und \(a_1\) mit ganzzahligen Koeffizienten schreiben, und somit zwei ganze Zahlen \(x,y\in\Z\) finden mit

\[\ggT(a,b) \ = \ a_n \ = \ xa_0 + ya_1 \ = \ xa + yb.\]

◻

Für eine geringe Schrittzahl \(n\in\N\) des euklidischen Algorithmus lässt sich das beschriebene Verfahren auch manuell gut durchführen, wie folgendes Beispiel zeigt.

Beispiel 2.15 (Linearkombination für den ggT)

Für die Zahlen \(a:=10\) und \(b:=7\) liefert der euklidische Algorithmus das Schema

\[\begin{aligned} 10 &=& 1\cdot 7+3,\\ 7 &=& 2\cdot 3+1,\\ 3 &=&3\cdot 1+0. \end{aligned}\]

Beginnend mit der vorletzten Zeile können wir nun schreiben

\[1 \ = \ 7-2\cdot 3 \ = \ 7-2\cdot (10-1\cdot 7) \ = \ -2\cdot 10 +3\cdot 7.\]

Wir finden also die ganzen Zahlen \(x=-2\) und \(y=3\), so dass

\[\ggT(a,b) \ = \ 1 \ = \ -2 \cdot 10 + 3 \cdot 7 \ = \ xa + yb.\]

Folgender Satz beschreibt eine Äquivalenzbedingung für die allgemeine Existenz von Lösungen für lineare diophantische Gleichungen.

Satz 2.6 (Lösungen von linearen diophantischen Gleichungen)

Seien zwei ganzzahlige Koeffizienten \(a,b\in\Z\) mit \((a,b)\ne (0,0)\) gegeben und sei \(c \in \Z\). Dann gelten die folgenden Aussagen für die Lösungsmenge von linearen diophantischen Gleichungen:

  1. Die lineare diophantische Gleichung \(ax+by=c\) ist genau dann lösbar, wenn gilt: \(\ggT(a,b) | c\).

  2. Gilt \(\ggT(a,b) | c\) und ist für zwei ganze Zahlen \(u,v\in\Z\) die spezielle diophantische Gleichung \(au+bv=\ggT(a,b)\) erfüllt, so lässt sich die unendliche Lösungsmenge von ganzen Zahlen der linearen diophantischen Gleichung angeben als:

    \[\begin{split} \{(x,y)\in \ &\Z\times\Z:ax+by=c\}\\ &= \{(\frac{c}{\ggT(a,b)}u+\frac{b}{\ggT(a,b)}m, \ \frac{c}{\ggT(a,b)}v-\frac{a}{\ggT(a,b)}m):m\in\Z\}. \end{split}\]

Proof. Wir definieren zunächst \(d := \ggT(a,b)\), \(a = da'\) und \(b = db'\) mit \(a',b'\in\Z\). Aus Satz 2.5 wissen wir bereits, dass zwei ganze Zahlen \(u,v \in \Z\) existieren, so dass gilt:

(2.4)#\[au+bv \ = \ d\]

Mit diesen Bezeichnungen können wir die beiden Aussagen des Satzes im Folgenden beweisen.

  1. Hinrichtung: Seien \(x,y\in\Z\) eine Lösung der linearen diophantischen Gleichung mit \(c=ax+by\). Dann folgt

    \[c \ = \ ax + by \ = \ da'x + db'y \ = \ d \cdot (a'x+b'y)\]

    Dies ergibt sofort die Behauptung \(\ggT(a,b) | c\).
    Rückrichtung: Es gelte nun umgekehrt \(\ggT(a,b)|c\), also existiert ein \(e \in \Z\) mit \(c=de\). Dann multiplizieren wir die spezielle diophantische Gleichung (2.4) mit \(e = \frac{c}{d} \in \Z\) auf beiden Seiten und erhalten somit

    \[a(ue)+b(ve) \ = \ de \ = \ c.\]

    Die Gleichung \(ax+by=c\) ist also lösbar mit \(x=ue\) und \(y=ve\).

    Anders geschrieben sehen wir also, dass folgendes Paar \(x,y \in Z\) von ganzen Zahlen die lineare diophantische Gleichung löst, wenn \(d|c\):

    \[(x,y) \ = \ (\frac{c}{\ggT(a,b)}u,\frac{c}{\ggT(a,b)}v).\]

  2. Man sieht leicht ein, dass die Inklusion \(\supseteq\) gilt, da wir bereits aus der ersten Aussage wissen, dass im Fall \(d|c\) gilt:

    \[a \cdot \frac{c}{d} u + b \cdot \frac{c}{d} v = c.\]

    Setzen wir nun für eine beliebige ganze Zahl \(m \in \Z\) die Zahlen \(x,y \in \Z\) aus der Behauptung in die lineare diophantische Gleichung ein, so erhalten wir:

    \[a \cdot \left(\frac{c}{d} u + \frac{b}{d}m\right) + b \cdot \left(\frac{c}{d}v - \frac{a}{d}m\right) = \underbrace{a \cdot \frac{c}{d} u + b \cdot \frac{c}{d} v}_{=\,c} + m \cdot \underbrace{\left(\frac{ab}{d} - \frac{ba}{d}\right)}_{=\, 0} = c.\]


    Wir zeigen nun die umgekehrte Inklusion \(\subseteq\). Sei also nun \(x,y \in \Z\) mit \(ax+by=c\). Dann ist \(ax+by=a(ue)+b(ve)\), also \(a(x-ue)=b(ve-y)\) bzw. \(a'(x-ue)=b'(ve-y)\). Wegen \(b'|a'(x-ue)\) und \(\ggT(a',b')=1\) folgt \(b'|x-ue\), d.h. es existiert \(m\in\Z\) mit \(x-ue=mb'\). Einsetzen liefert dann \(ve-y=ma'\).

◻

Der spezielle Fall einer linearen diophantischen Gleichung mit zwei teilerfremden Koeffizienten \(a,b \in \Z\) ist für unsere Anwendungen in der Kryptographie besonders interessant.

Korollar 2.2 (Lösungen für teilerfremde Koeffizienten)

Sind \(a,b\in\Z\) teilerfremd, d.h. es gilt \(\ggT(a,b)=1\), so existiert eine ganzzahlige Lösung \(x_0,y_0\in\Z\) der linearen diophantischen Gleichung \(ax_0+by_0=1\) und es gilt für die Lösungsmenge

\[\{(x,y)\in\Z\times\Z:ax+by=1\} \ = \ \{(x_0+bm,y_0-am):m\in\Z\}.\]

2.3.4. Erweiterter euklidischer Algorithmus#

Das Vorgehen im Beweis von Satz 2.6 lässt sich in einer systematischen Form beschreiben, was im Folgenden zum erweiterten euklidischen Algorithmus führt.

Algorithmus 2.5 (Erweiterter euklidischer Algorithmus (Variante I))

Seien \(a,b\in\N_0\). Man definiert nun rekursiv Zahlenfolgen \(q_i,a_i,x_i,y_i \in \Z\) durch die folgende algorithmische Vorschrift:

  • Wir initialisieren zunächst die Zahlenfolgen als:

    \[a_0:=a, \quad a_1:=b, \quad x_0:=1, \quad x_1:=0, \quad y_0:=0, \quad y_1:=1.\]

  • Sind \(a_i,a_{i+1},x_i,x_{i+1},y_i,y_{i+1} \in \Z\) bereits definiert, so unterscheiden wir die folgenden beiden Fälle

    1. Ist \(a_{i+1}=0\), so terminiert der Algorithmus.

    2. Ist \(a_{i+1}>0\), so definieren wir

      \[q_i:=\floor{\frac{a_i}{a_{i+1}}}\quad\text{ und }\quad a_{i+2}:=a_i\bmod a_{i+1}\text{ (oder } a_{i+2}= a_i-q_ia_{i+1} \text{)}\]

      und

      \[x_{i+2}:=x_i-q_ix_{i+1}\quad\text{ und }\quad y_{i+2}:=y_i-q_iy_{i+1}.\]

Ist \(n\in\N_0\) der früheste Index für den \(a_{n+1}=0\) gilt, so kann man die Vorgehensweise in folgender Tabelle zusammenfassen:

\(a_0 = a\)

\(x_0=1\)

\(y_0=0\)

\(a_1 = b\)

\(x_1=0\)

\(y_1=1\)

\(q_0=\floor{\frac{a_0}{a_1}}\)

\(a_2=a_0-q_0a_1\)

\(x_2=x_0-q_0x_1\)

\(y_2=y_0-q_0y_1\)

⋮

⋮

⋮

⋮

\(\ast\)

\(a_i\)

\(x_i\)

\(y_i\)

\(\ast\)

\(a_{i+1}\)

\(x_{i+1}\)

\(y_{i+1}\)

\(q_i=\floor{\frac{a_i}{a_{i+1}}}\)

\(a_{i+2}=a_i-q_ia_{i+1}\)

\(x_{i+2}=x_i-q_ix_{i+1}\)

\(y_{i+2}=y_i-q_iy_{i+1}\)

⋮

⋮

⋮

⋮

\(\ast\)

\(a_{n-1}\)

\(x_{n-1}\)

\(y_{n-1}\)

\(\ast\)

\(a_n\)

\(x_n\)

\(y_n\)

\(q_{n-1}=\floor{\frac{a_{n-1}}{a_n}}=\frac{a_{n-1}}{a_n}\)

\(a_{n+1}=0\)

\(x_{n+1}\)

\(y_{n+1}\)

Das folgende Theorem zeigt, dass Algorithmus 2.5 nicht nur den größten gemeinsamen Teiler von \(a,b \in \N_0\) berechnet, sondern gleichzeitig auch eine Lösung \(x,y \in \Z\) der entsprechenden linearen diophantischen Gleichung bestimmt.

Satz 2.7 (Lösungsverhalten des erweiterten euklidischen Algorithmus)

Sei \(n\in\N_0\) der früheste Index für den \(a_{n+1}=0\) im erweiterten euklidischen Algorithmus gilt. Dann ist in jedem Schritt folgende lineare diophantische Gleichung erfüllt:

\[a_i \ = \ x_ia+y_ib\quad\text{ für }\quad 0\le i\le n+1.\]

Insbesondere erhält man im vorletzten Schritt:

\[\ggT(a,b) \ = \ a_n \ = \ x_na+y_nb.\]

Proof. Die Aussage \(a_n = \ggT(a,b)\) haben wir bereits beim euklidischen Algorithmus gezeigt.

Wir nummerieren die Zeilen der Tabelle in Algorithmus 2.5 von \(0\) bis \(n+1\) durch. Nun zeigen wir durch Induktion, dass gilt

\[a_i=x_ia+y_ib \quad \text{ für } \quad i=0,\dots,n+1.\]

Induktionsanfang: Für \(i=0\) und \(i=1\) folgt die Aussage aus der Definition von \(x_0,y_0,x_1,y_1\).
Induktionsschritt: Ist nun \(i\ge 0\) und die Aussage sei bereits für \(i\) und \(i+1\) gezeigt, also

\[\begin{aligned} a_i &=& x_ia+y_ib, \\ a_{i+1} &=& x_{i+1}a+y_{i+1}b, \end{aligned}\]

so folgt sofort

\[\begin{aligned} x_{i+2}a+y_{i+2}b &=& (x_i-q_ix_{i+1})a+(y_i-q_iy_{i+1})b\\ &=& (ax_i+y_ib) - q_i(x_{i+1}a+y_{i+1}b)= a_i-q_ia_{i+1}=a_{i+2}, \end{aligned}\]

was die Behauptung zeigt. ◻

Bemerkung 2.5 (Berechnungsschema für den erweiterten euklidischen Algorithmus)

Das in Algorithmus 2.5 angegebene Verfahren lässt sich auch manuell recht einfach durchführen. Seien zunächst \(a,b\in\N_0\) gegeben.

  • Initialisierung: Lege eine Tabelle mit vier Spalten für die Werte von \(q_i, a_i, x_i, y_i\) an. In die ersten beiden Zeilen trägt man folgende Werte ein, wobei die erste Spalte (für die Quotienten) noch frei bleibt:

    \(q\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    \(a\)

    \(1\)

    \(0\)

    \(b\)

    \(0\)

    \(1\)

  • Schleife: Hat man die Zeilen \(i\) und \(i+1\) bereits bestimmt, wobei die Zählung mit \(i=0\) begonnen wird, und ist \(a_{i+1}\ne 0\), so berechnet man die nächste Zeile \(i+2\) wie folgt:

    ⋮

    ⋮

    ⋮

    ⋮

    \(\ast\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    \(\ast\)

    \(a_{i+1}\)

    \(x_{i+1}\)

    \(y_{i+1}\)

    \(q_i=\floor{\frac{a_{i}}{a_{i+1}}}\)

    \(a_{i+2}=a_i-q_ia_{i+1}\)

    \(x_{i+2}=x_i-q_ix_{i+1}\)

    \(y_{i+2}=y_i-q_iy_{i+1}\)

    Man berechnet also zunächst den abgerundeten Quotienten \(q_i=\floor{\frac{a_i}{a_{i+1}}}\) und anschließend damit \(a_{i+2},x_{i+2},y_{i+2}\). Hierbei kann man ausnutzen, dass \(a_{i+2}=a_i-q_ia_{i+1} = a_i\bmod a_{i+1}\) ist.

  • Terminierung: Falls \(a_{i+1}=0\) gilt, so ist man in folgender Situation:

    ⋮

    ⋮

    ⋮

    ⋮

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    \(q_{i-1}\)

    \(a_{i+1}=0\)

    \(x_{i+1}\)

    \(y_{i+1}\)

    In diesem Fall ist man fertig, denn es gilt \(a_i=x_ia+y_ib\) und \(a_i=\ggT(a,b)\). Die Werte \(x_{i+1}\) und \(y_{i+1}\) muss man nicht mehr berechnen im letzten Schritt, da sie nicht benötigt werden.

Wir wenden das manuelle Berechnungsschema aus Bemerkung 2.5 auf einige Beispiele im Folgenden an.

Beispiel 2.16 (Manuelle Durchführung des erw. euklidischen Algorithmus)

  1. Seien \(\mathbf{a=14}\) und \(\mathbf{b=11}\). Dann berechnen wir:

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    14

    1

    0

    11

    0

    1

    1

    3

    1

    -1

    3

    2

    -3

    4

    1

    1

    4

    -5

    2

    0

    -11

    14

    Die Zahlen der vorletzten Zeile liefern uns also

    \[1=\ggT(a,b)=4\cdot a-5\cdot b\]

  2. Seien \(\mathbf{a=12345}\) und \(\mathbf{b=987}\). Dann berechnen wir:

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    12345

    1

    0

    987

    0

    1

    12

    501

    1

    -12

    1

    486

    -1

    13

    1

    15

    2

    -25

    32

    6

    -65

    813

    2

    3

    132

    -1651

    2

    0

    -329

    4115

    Die Zahlen der vorletzten Zeile liefern uns also

    \[3=\ggT(a,b)=132\cdot a-1651\cdot b\]

  3. Seien \(\mathbf{a=8462}\) und \(\mathbf{b=3876}\). Dann berechnen wir:

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    8462

    1

    0

    3876

    0

    1

    2

    710

    1

    -2

    5

    326

    -5

    11

    2

    58

    11

    -24

    5

    36

    -60

    131

    1

    22

    71

    -155

    1

    14

    -131

    286

    1

    8

    202

    -441

    1

    6

    -333

    727

    1

    2

    535

    -1168

    3

    0

    -1938

    4231

    Die Zahlen der vorletzten Zeile liefern uns also

    \[2=\ggT(a,b)=535\cdot a-1168\cdot b\]

    Nun tauschen wir die Zahlen, d.h., es sei \(\mathbf{a=3876}\) und \(\mathbf{b=8462}\). Dann berechnen wir:

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    3876

    1

    0

    8462

    0

    1

    0

    3876

    1

    0

    2

    710

    -2

    1

    5

    326

    11

    -5

    2

    58

    -24

    11

    5

    36

    131

    -60

    1

    22

    -155

    71

    1

    14

    286

    -131

    1

    8

    -441

    202

    1

    6

    727

    -333

    1

    2

    -1168

    535

    3

    0

    4231

    -1938

    Die Zahlen der vorletzten Zeile liefern uns also

    \[2=\ggT(a,b)=-1168\cdot a+535\cdot b\]

  4. Seien \(\mathbf{a=1234567}\) und \(\mathbf{b=7654321}\). Dann berechnen wir:

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    1234567

    1

    0

    7654321

    0

    1

    0

    1234567

    1

    0

    6

    246919

    -6

    1

    4

    246891

    25

    -4

    1

    28

    -31

    5

    8817

    15

    273352

    -44089

    1

    13

    -273383

    44094

    1

    2

    546735

    -88183

    6

    1

    -3553793

    573192

    2

    0

    7654321

    -1234567

    Die Zahlen der vorletzten Zeile liefern uns also

    \[1=\ggT(a,b)=-3553793\cdot a+573192\cdot b\]

  5. Seien \(\mathbf{a=987654321}\) und \(\mathbf{b=123456789}\). Dann berechnen wir:

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    987654321

    1

    0

    123456789

    0

    1

    8

    9

    1

    -8

    13717421

    0

    -13717421

    109739369

    Die Zahlen der vorletzten Zeile liefern uns also

    \[9=\ggT(a,b)=1\cdot a-8\cdot b\]

  6. Das Berechnungsschema funktioniert auch, wenn \(a=0\) oder \(b=0\) gilt. Seien \(\mathbf{a=2}\) und \(\mathbf{b=0}\). Dann berechnen wir:

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    2

    1

    0

    0

    0

    1

    Die Zahlen der vorletzten Zeile liefern uns also

    \[2=\ggT(a,b)=1\cdot a+0\cdot b\]

    Umgekehrt erhält man für \(\mathbf{a=0}\) und \(\mathbf{b=2}\):

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    0

    1

    0

    2

    0

    1

    0

    0

    1

    0

    Die Zahlen der vorletzten Zeile liefern uns also

    \[2=\ggT(a,b)=0\cdot a+1\cdot b\]

    Im Spezialfall \(\mathbf{a=0}\) und \(\mathbf{b=0}\) ergibt sich

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    0

    1

    0

    0

    0

    1

    Die Zahlen der vorletzten Zeile liefern uns also

    \[0=\ggT(a,b)=1\cdot a+0\cdot b\]

  7. Seien \(\mathbf{a=15847523452462634165}\) und \(\mathbf{b=87648572364875263842}\). Dann berechnen wir:

    \(q_{i-2}\)

    \(a_i\)

    \(x_i\)

    \(y_i\)

    15847523452462634165

    1

    0

    87648572364875263842

    0

    1

    0

    15847523452462634165

    1

    0

    5

    8410955102562093017

    -5

    1

    1

    7436568349900541148

    6

    -1

    1

    974386752661551869

    -11

    2

    7

    615861081269678065

    83

    -15

    1

    358525671391873804

    -94

    17

    1

    257335409877804261

    177

    -32

    1

    101190261514069543

    -271

    49

    2

    54954886849665175

    719

    -130

    1

    46235374664404368

    -990

    179

    1

    8719512185260807

    1709

    -309

    5

    2637813738100333

    -9535

    1724

    3

    806070970959808

    30314

    -5481

    3

    219600825220909

    -100477

    18167

    3

    147268495297081

    331745

    -59982

    1

    72332329923828

    -432222

    78149

    2

    2603835449425

    1196189

    -216280

    27

    2028772789353

    -32729325

    5917709

    1

    575062660072

    33925514

    -6133989

    3

    303584809137

    -134505867

    24319676

    1

    271477850935

    168431381

    -30453665

    1

    32106958202

    -302937248

    54773341

    8

    14622185319

    2591929365

    -468640393

    2

    2862587564

    -5486795978

    992054127

    5

    309247499

    30025909255

    -5428911028

    9

    79360073

    -275719979273

    49852253379

    3

    71167280

    857185847074

    -154985671165

    1

    8192793

    -1132905826347

    204837924544

    8

    5624936

    9920432457850

    -1793689067517

    1

    2567857

    -11053338284197

    1998526992061

    2

    489222

    32027109026244

    -5790743051639

    5

    121747

    -171188883415417

    30952242250256

    4

    2234

    716782642687912

    -129599712052663

    54

    1111

    -38877451588562665

    7029336693094058

    2

    12

    78471685819813242

    -14188273098240779

    92

    7

    -7258272547011380929

    1312350461731245726

    1

    5

    7336744232831194171

    -1326538734829486505

    1

    2

    -14595016779842575100

    2638889196560732231

    2

    1

    36526777792516344371

    -6604317127950950967

    2

    0

    -87648572364875263842

    15847523452462634165

    Die Zahlen der vorletzten Zeile liefern uns also

    \[1=\ggT(a,b)=36526777792516344371\cdot a-6604317127950950967\cdot b\]

Bei der oben beschriebenen Methode zur Durchführung des erweiterten euklidischen Algorithmus berechnet man bei Kenntnis der Zahlen \(a_i,x_i,y_i \in \Z\) und \(a_{i+1},x_{i+1},y_{i+1} \in \Z\) die neuen Werte \(q_i, a_{i+2},x_{i+2},y_{i+2} \in \Z\) mittels

\[a_{i+2}=a_i-qa_{i+1},\quad x_{i+2}=x_i-qx_{i+1},\quad y_{i+2}=y_i-qy_{i+1}\quad\text{ mit }\quad q_i=\floor{\frac{a_i}{a_{i+1}}}.\]

Da immer nur die beiden letzten Elemente der Liste von berechneten Zahlen benötigt werden, lässt sich der erweiterte euklidische Algorithmus wie folgt in Python realisieren:

def eea(a,b): 
  q=[]
  a=[a,b]
  x=[1,0]
  y=[0,1]
  while a[-1]>0:
    q=a[-2]//a[-1]
    a.append(a[-2]-q*a[-1])
    x.append(x[-2]-q*x[-1])
    y.append(y[-2]-q*y[-1])
  return a[-2],x[-2],y[-2]

Ein (kleiner) Nachteil der vorangegangenen Variante des erweiterten euklidischen Algorithmus ist, dass man die Folgen \(q_{i-2}, a_i,x_i,y_i\) für \(i=0,\ldots,n+1\) speichert. Für eine effizientere Implementierung ist es bequem zusätzliche Hilfsvariablen \(b_i, x_i', y_i' \in \Z\) einzuführen mit:

\[b_i=a_{i+1},\quad x_i'=x_{i+1},\quad y_i'=y_{i+1}\]

Damit erhält man die folgende Variante des erweiterten euklidischen Algorithmus.

Algorithmus 2.6 (Erweiterter euklidischer Algorithmus (Variante II))

Seien \(a,b\in\N_0\) gegeben. Wir definieren dann rekursiv Zahlenfolgen \(a_i,b_i,x_i,x_i',y_i,y_i' \in \Z\) wie folgt:

  • \(a_0=a, \quad b_0=b, \quad x_0=1, \quad x_0'=0, \quad y_0=0, \quad y_0'=1\).

  • Sind die Zahlen \(a_i,b_i,x_i,x_i',y_i,y_i'\in\Z\) bereits bekannt, so unterscheiden wir die folgenden beiden Fälle:

    • Ist \(b_i=0\), so terminiert der Algorithmus.

    • Ist \(b_i>0\), so definieren wir

      \[q_i=\floor{\frac{a_i}{b_i}}\]

      und berechnen damit die nächsten Zahlen als:

      \[\begin{aligned} a_{i+1}&=&b_i,\\ b_{i+1}&=&a_i-q_ib_i =a_i\bmod b_i,\\ x_{i+1}&=&x_i',\\ x_{i+1}'&=&x_i-q_ix_i',\\ y_{i+1}&=&y_i',\\ y_{i+1}'&=&y_i-q_iy_i'. \end{aligned}\]

In Python lässt sich diese Variante des erweiterten euklidischen Algorithmus realisieren als:

def eea_v2(a,b): 
  x,y = 1,0 
  xx,yy = 0,1
  while b>0:
    q = a//b
    a,b = b,a-q*b      # alternativ: a,b = b,a%b
    x,xx = xx,x-q*xx
    y,yy = yy,y-q*yy
  return a,x,y
Inhalt