Der größte gemeinsame Teiler und der Euklidische Algorithmus

Ausgehend von der Frage, welcher Zusammenhang zwischen Multiplikationstabellen und Linearkombinationen in den ganzen Zahlen bestehen, werden der Euklidische Algorithmus und seine Erweiterung besprochen. Der Euklidische Algorithmus berechnet den größten gemeinsamen Teiler zweier Zahlen, der erweiterte Euklidische Algorithmus erlaubt es zusätzlich, den größten gemeinsamen Teiler von a und b als Linearkombination von a und b darzustellen. Die Analyse dieser Algorithmen liefert zahlreiche Einsichten in die Zusammenhänge zwischen Kongruenzen, Linearkombination in Z und den Eigenschaften des größten gemeinsamen Teilers zweier Zahlen. In den R-Skripten werden Implementierungen vorgestellt sowie Verbesserungen (Blankinship, Stein) des Euklidischen Algorithmus diskutiert.

walter
Algorithmus von Stein ggT größter gemeinsamer Teiler Euklidischer Algorithmus Blankinship-Algorithmus Linearkombination in Z erweiterter Euklidischer Algorithmus Multiplikationstabelle gcd
Inhaltsverzeichnis

Einordnung des Artikels

Diese Kapitel setzt die Kenntnis der Ganzzahl-Division, der Kongruenz und der Teilbarkeitsrelation voraus, die in den Kapiteln Ganzzahl-Division: Kongruenzen und Restklassen als Beispiele für Äquivalenzrelationen und Äquivalenzklassen, Rechnen mit Restklassen: Teilbarkeitsregeln und Die Teilbarkeitsrelation als Ordnungsrelation besprochen wurden.

Einführung

Eng verknüpft mit Fragen rund um das Thema Teilbarkeit ist der größte gemeinsame Teiler zweier Zahlen. Versucht man zum Beispiel Multiplikationstabellen zu verallgemeinern, wird man zwangsläufig zu diesem Begriff geführt. Für kleine Zahlen a und b kann man den größten gemeinsamen Teiler von a und b leicht erraten oder aus der Primfaktorzerlegung von a und b ablesen. Für große Zahlen liefert der Euklidische Algorithmus ein einfaches Verfahren den größten gemeinsamen Teiler von a und b zu bestimmen. Dieser und ähnliche Algorithmen werden vorgestellt und in R implementiert

Da es zahlreiche Anwendungen des größten gemeinsamen Teilers gibt, die hier noch nicht besprochen werden, ist der Euklidische Algorithmus in vielerlei Hinsicht interessant:

Linearkombinationen in den ganzen Zahlen

Multiplikationstabellen und ihre Verallgemeinerung durch Linearkombinationen

Die Bildung von Restklassen durch die Kongruenz kann man sehr gut an den Multiplikationstabellen darstellen: Eine Spalte einer Multiplikationstabelle besteht aus den Vielfachen einer Zahl a ∈ Z, also aus einer Menge

M(a) = {k · a : k ∈ Z}.

Formuliert man – wie üblich – die Kongruenz über die Division, dann würde man schreiben:

M(a) = R[0] (mod a).

Die Menge M(a) ist also die Menge aller ganzen Zahlen, die bei Division durch a den Rest 0 besitzen.

Die Bildung der Menge M(a) kann man folgendermaßen verallgemeinern: Man gibt sich zwei Zahlen a, b ∈ Z vor und bildet alle möglichen Linearkombinationen in Z:

LK(a, b) = {k · a + l · b : k, l ∈ Z}.

Der Begriff der Linearkombination wurde in Die Teilbarkeitsrelation als Ordnungsrelation eingeführt und dort wurde in Satz 2 gezeigt: Ist d sowohl Teiler von a als auch von b, dann ist d auch Teiler von jeder Linearkombination von a und b.

Verknüpft man diesen Satz jetzt noch mit den Hasse-Diagrammen, so drängen sich weitere Fragen über LK(a, b) auf.

Abbildung 1 zeigt nochmals das Hasse-Diagramm aller (positiven) Teiler von a = 24 und b = 18 (in Die Teilbarkeitsrelation als Ordnungsrelation war dies Abbildung 10).

Abbildung 1: Hasse-Diagramm für die positiven Teiler von 24 und 18.Abbildung 1: Hasse-Diagramm für die positiven Teiler von 24 und 18.

Man erkennt, daran dass 1, 2, 3 und 6 die gemeinsamen Teiler von a = 24 und b = 18 sind. Nach dem oben zitierten Satz 2 sind diese Zahlen somit auch Teiler jeder Zahl aus LK(a = 24, b = 18).

Die naheliegenden weiteren Fragen sind dann:

  1. Gibt es auch andere Zahlen, die nur Teiler von entweder a = 24 oder b = 18 sind (wie etwa 4), die dennoch Teiler aller Zahlen aus LK(a, b) sind?
  2. Wie kann man die Menge LK(a = 24, b = 18) einfach charakterisieren? Gibt es etwa einen Zusammenhang mit den Restklassen?
  3. Offensichtlich ist 6 in der Menge LK(a = 24, b = 18) enthalten, da 6 = 24 - 18. Wie kann man zu einer gegebenen Zahl z ∈ LK(a = 24, b = 18) die Koeffizienten k und l berechnen, so dass z = k · 24 + l · 18?
  4. Nach dem letzten Punkt ist klar, dass a - b immer in LK(a, b) enthalten ist; ebenso ist 0 ∈ LK(a, b). Nicht klar ist allerdings, ob es weitere ganze Zahlen zwischen 0 und a - b gibt, die in LK(a, b) enthalten sind. Oder speziell: Welches ist die kleinste natürliche Zahl in LK(a, b)?
  5. Man möchte diese Fragen natürlich nicht nur für den Spezialfall a = 24 und b = 18 beantworten, sondern für beliebige Zahlen a, b und ihre Linearkombinationen LK(a, b). Die ersten beiden Fragen und die vierte Frage sollte zu einer Charakterisierung von LK(a, b) führen – ähnlich wie man die Spalten einer Multiplikationstabelle mit Restklassen charakterisiert. Die dritte Frage sollte zu einem Algorithmus führen, mit dem man die gesuchten Koeffizienten berechnen kann.

Und wenn man diese Fragen beantwortet hat, kann man die Fragestellung natürlich nochmals verallgemeinern und Linearkombinationen von beliebig vielen Zahlen bilden.

Eigenschaften von Linearkombinationen in den ganzen Zahlen

Die im letzten Unterabschnitt formulierten Fragen sollen jetzt als Leitfaden dienen, um die Eigenschaften der Linearkombinationen zweier gegebener Zahlen a und b zu untersuchen. Zuerst soll eine geometrische Interpretation der Linearkombination vorgestellt werden, die die folgenden Sätze über die Linearkombinationen besser verständlich macht.

Die Menge M(a) der ganzzahligen Vielfachen einer Zahl a, kann man mit einem Maßstab der Länge a veranschaulichen: Durch Aneinanderlegen des Maßstabes kann man die Längen 2a, 3a, 4a und so weiter erzeugen (siehe Abbildung 2 oben). Um Längen wie a/2, a/3 oder a + a/3 zu erzeugen, benötigt man ein weiteres Hilfsmittel, das den Maßstab halbiert oder drittelt.

Entsprechend kann man die Menge LK(a, b) interpretieren: Man hat zwei Maßstäbe der Längen a und b zur Verfügung; durch Aneinanderlegen kann man die Längen a + b, 2a + b, 2a + 2b und so weiter erzeugen (siehe Abbildung 2 unten links).

Abbildung 2: Abstände, die man mit Hilfe eines Maßstabes der Länge a (oben) beziehungsweise mit zwei Maßstäben der Längen a und b (unten links) erzeugen kann. Unten rechts ist ein gemeinsamer Teiler d von a und b dargestellt. Die Längen der Maßstäbe sind hier so gewählt, dass a und b die Werte aus dem Hasse-Diagramm aus Abbildung 1 annehmen können (dann ist d = 6).Abbildung 2: Abstände, die man mit Hilfe eines Maßstabes der Länge a (oben) beziehungsweise mit zwei Maßstäben der Längen a und b (unten links) erzeugen kann. Unten rechts ist ein gemeinsamer Teiler d von a und b dargestellt. Die Längen der Maßstäbe sind hier so gewählt, dass a und b die Werte aus dem Hasse-Diagramm aus Abbildung 1 annehmen können (dann ist d = 6).

Der folgende Satz 1 beschreibt die Eigenschaften von LK(a,b), die sofort aus der Definition folgen.

Satz 1:

Sind a, b ∈ Z und LK(a, b) = {k · a + l · b : k, l ∈ Z}. Dann gilt:

  1. Ist a = b oder b = 0, dann ist LK(a, b) = M(a).
  2. Es ist LK(a, b) = LK(-a, b) = LK(a, -b) = LK(-a, -b).
  3. Die Vielfachen von a und b sind in LK(a, b) enthalten: M(a) ∪ M(b) ⊆ LK(a, b).
  4. Ist d ein gemeinsamer Teiler von a und b, dann ist d Teiler aller Elemente von LK(a, b): d|a und d|b ⇒ d|z für alle z ∈ LK(a, b).
  5. Ist d kein gemeinsamer Teiler von a und b, dann kann d nicht Teiler von allen Elementen aus LK(a, b) sein.
  6. Ist z ∈ LK(a, b) mit z = k · a + l · b, dann kann z auch mit den Koeffizienten k' = k - b und l' = l + a dargestellt werden: z = k' · a + l' · b.
  7. Zu jeder Zahl z ∈ LK(a, b) gibt es unendlich viele Darstellungen in der Form z = k · a + l · b.

Beweis von Satz 1:

  1. Klar, da die Elemente von LK(a, a) und LK(a, 0) Vielfache von a sind. Man beachte, dass die Bedingung a = b oder b = 0 in der Bedingung a ≡ b (mod a) enthalten ist. Die Aussage gilt natürlich für alle b mit a ≡ b (mod a).
  2. Man muss nur in den Koeffizienten k, l die Vorzeichen entsprechend anpassen.
  3. M(a) = {k · a + l · b : k ∈ Z, l = 0}, M(b) = {k · a + l · b : l ∈ Z, k = 0}.
  4. Oben wurde schon auf den Satz hingewiesen, wonach die gemeinsamen Teiler von a und b auch Teiler jeder Linearkombination von a und b sind.
  5. Ist d Teiler von a, aber nicht von b, so muss man nur die Linearkombination von a und b mit k = 0 und l = 1 wählen. Damit hat man eine Zahl gefunden, die in LK(a, b) enthalten ist, aber d ist kein Teiler von ihr. (Analog mit Vertauschung von a und b.)
  6. Ist z = k · a + l · b, dann ist k' · a + l' · b = (k - b) · a + (l + a) · b = k · a - b · a + l · b + a · b = k · a + l · b = z.
  7. Iteriert man die letzte Aussage beliebig oft, erhält man beliebig viele Darstellungen für eine Zahl z, wenn eine einzige Darstellung gegeben ist. Man kann in der letzten Aussage auch die Vorzeichen vertauschen: Auch (k + b) · a + (l - a) · b ist eine mögliche Darstellung von z, womit man den Koeffizienten beliebiges Vorzeichen geben kann.

Auch einen gemeinsamen Teiler d von a und b kann mit Hilfe der Maßstäbe veranschaulichen: In Abbildung 2 rechts ist ein Maßstab der Länge d gezeigt, für den gilt:

4d = a und 3d = b.

Aufgabe:

Veranschaulichen Sie die Aussagen von Satz 1 mit Hilfe der Maßstäbe wie in Abbildung 2.

Versuchen Sie eine Charakterisierung der Menge LK(a = 24, b = 18) zu geben.

♦ ♦ ♦ ♦ ♦

Aus Satz 1 ergibt sich noch nicht die gesuchte einfache Charakterisierung der Menge LK(a, b). Es sollte aber klar sein, dass die gemeinsamen Teiler von a und b einen Zugang zu weiteren Eigenschaften von LK(a, b) liefern können. Den Schlüssel dazu liefert der folgende Satz 2, für den gelten soll, dass

a > b > 0.

Aus Satz 1 kann man dann leicht folgern, wie man Satz 2 umformulieren müsste, so dass er für beliebige ganze Zahlen a und b gilt.

Weiter werden im Folgenden immer nur die positiven Teiler einer Zahl benötigt; sie werden dennoch kurz als die Teiler der Zahl bezeichnet. Am Ende kann man sich überlegen, dass die formulierten Sätze auch ihre Gültigkeit behalten, wenn man negative Teiler zulässt – lediglich umständliche Formulierungen und Fallunterscheidungen müssten verwendet werden.

Satz 2:

Sind a und b natürliche Zahlen mit a > b > 0, dann gilt:

  1. Ist b Teiler von a, dann ist LK(a, b) = M(b).
  2. Ist b kein Teiler von a und die Ganzzahl-Division a ÷ b liefert den Rest r, mit r ∈ {1, 2, ..., b - 1}, dann ist jeder gemeinsame Teiler von a und b auch Teiler von r. Die Zahl r ist in LK(a, b) enthalten.
  3. Da a und b nur endlich viele gemeinsame Teiler haben, gilt die zweite Aussage insbesondere für den größten gemeinsamen Teiler von a und b.

♦ ♦ ♦ ♦ ♦

Satz 2 soll erst später bewiesen werden. Zunächst sollen ihn drei einfache Beispiele veranschaulichen.

Beispiele:

1. Beispiel: a = 24 und b = 18

Dieser Fall ist in Abbildung 1 als Hasse-Diagramm dargestellt und die Maßstäbe in Abbildung 2 könnten die Längen a und b besitzen. Teilt man jetzt a durch b, so erhält man:

a ÷ b = 24 ÷ 18 = 1 Rest 6.

Der Rest r = 6 beitzt alle gemeinsamen Teiler von a = 24 und b = 18, nämlich 1, 2, 3, 6.

Schreibt man die Division a ÷ b = q + r als Multiplikation, lautet sie:

a = b · q + r, hier also: 24 = 18 + 6 oder 6 = 24 - 18.

Die letzte Darstellung der Zahl 6 zeigt aber, dass sie in LK(a = 24, b = 18) enthalten ist (wähle die Koeffizienten k = 1 und l = -1).

2. Beispiel: a = 34 und b = 24

Die Zahlen a und b besitzen nur 1 und 2 als gemeinsame Teiler. Die Ganzzahl-Division liefert:

a ÷ b = 34 ÷ 24 = 1 Rest 10.

Der Rest r = 10 besitzt die beiden Teiler 1 und 2. Und wiederum kann man schreiben:

10 = 34 - 24,

woraus folgt, dass 10 ∈ LK(a = 34, b = 24).

3. Beispiel: a = 34 und b = 3

Jetzt besitzen a und b lediglich den gemeinsamen Teiler 1. Es gilt:

a ÷ b = 34 ÷ 3 = 11 Rest 1.

Aber dennoch beitzt der Rest r = 1 alle gemeinsamen Teiler von a und b und r kann als Linearkombination von a und b dargestellt werden:

r = 34 - 3 · 11.

Beweis von Satz 2

Teil 1:

Ist b Teiler von a, dann gibt es ein q ∈ Z mit q · b = a.

Ist z ∈ LK(a, b), dann ist als

z = k · a + l · b

darstellbar. Mit obigem q wird dies zu

z = k · q · b + l · b = (k · q + l) · b ∈ M(b).

Also ist LK(a, b) ⊆ M(b).

Die umgekehrte Inklusion ist trivial: sie gilt immer, auch wenn b kein Teiler von a ist; man muss nur die Linearkombinationen mit k = 0 wählen.

Teil 2:

Es wird vorausgesetzt, dass

a ÷ b = q Rest r.

Aufgelöst nach r:

r = a - q · b

Ist jetzt d ein gemeinsamer Teiler von a und b, so gibt es natürliche Zahlen s und t mit:

a = s · d, b = t · d.

Es folgt für r:

r = s · d - q · t · d = (s - q · t) · d.

Folglich ist d Teiler von r. Und obige Darstellung von r zeigt sofort, dass r ∈ LK(a, b).

Teil 3:

Die Begründung ist schon im Satz gegeben.

Der größte gemeinsame Teiler

Der folgenden Sätze 3 und 4 werden die gesuchte Charakterisierung der Menge der Linearkombinationen zweier ganzer Zahlen geben. Die Sätze lassen sich leichter formulieren, wenn der Begriff des größten gemeinsamen Teilers zweier ganzer Zahlen einführt.

Definition: Sind a und b zwei ganze Zahlen, dann wird die größte ganze Zahl d mit d|a und d|b als der größte gemeinsame Teiler von a und b, kurz gcd(a, b), bezeichnet.

♦ ♦ ♦ ♦ ♦

Die Bezeichnung gcd stammt von greatest common divisor. Die andere häufig benutzte Bezeichnung ist ggT.

Weiter unten werden dann die Eigenschaften von gcd(a, b) formuliert; zunächst soll die Menge der Linearkombinationen von a und b charakterisiert werden.

Der erweiterte Euklidische Algorithmus

Der oben formulierte Satz 2 wirkt sehr einfach und wenig hilfreich, um die Linearkombinationen besser zu verstehen. Im Folgenden wird ein Iterationsverfahren angegeben, das einen Zusammenhang zwischen dem größten gemeinsamen Teiler von a und b und der Menge LK(a, b) herstellen wird; das Iterationsverfahren wird üblicherweise als der erweiterte Euklidische Algorithmus bezeichnet.

Erweiterter Euklidischer Algorithmus:

  1. Ausgangspunkt sind zwei natürliche Zahlen a ≥ b > 0.
  2. Falls a = b oder b|a ist der Algorithmus beendet. Letzteres ist zugleich die Abbruchbedingung für den Algorithmus. Falls b kein Teiler von a ist, werden die folgenden Schritte ausgeführt.
  3. Im folgenden Iterationsverfahren werden die Zahlen a und b immer wieder neu gesetzt. Am Ende erhält man den größten gemeinsamen Teiler von a und b, also gcd(a, b) und die Koeffizienten k und l, mit denen gcd(a, b) als Linearkombination von a und b dargestellt werden kann: gcd(a, b) = k · a + l · b.
    1. Man berechnet (Ganzzahl-Division) a ÷ b. Das Ergebnis kann eindeutig in der Form q1 b + r1 geschrieben werden, wobei q1 ≥ 0 und r1 = 1, 2, ..., b - 1. Im ersten Schritt kann r1 nicht gleich null sein (sonst wäre schon bei Schritt 2 das Ende des Algorithmus erreicht).
    2. Man ersetzt die Startwerte a und b durch b und r1 und berechnet b ÷ r1 = q2 r1 + r2. Der Rest r2 kann jetzt die Werte 0, 1, 2, ..., b - 1 annehmen.
    3. Der letzte zwei Schritte werden solange wiederholt bis ein Rest rn = 0.
    4. Ist rn = 0, so gilt: gcd(a, b) = rn-1. Aus den berechneten Werten qi und ri können die Koeffizienten k und l berechnet werden, mit denen gcd(a, b) als Linearkombination von a und b dargestellt werden kann: gcd(a, b) = k · a + l · b. Wie diese Berechnung erfolgt, wird unten gezeigt. Für den Fall, dass der Algorithmus schon im zweiten Schritt beendet ist, gilt: gcd(a, b) = b (damit ist gcd(a, b) als Linearkombination von a und b gegeben).

Die folgende Tabelle soll die Rechenschritte veranschaulichen:

1. Schritt: (a, b) a ÷ b = q1 b + r1 r1 = a - q1 b
2. Schritt: (b, r1) b ÷ r1 = q2 r1 + r2 r2 = b - q2 r1
3. Schritt: (r1, r2) r1 ÷ r2 = q3 r2 + r3 r3 = r1 - q3 r2
...
i-ter Schritt: (ri-2, ri-1) ri-2 ÷ ri-1 = qi ri-1 + ri ri = ri-2 - qi ri-1
...
(n-1)-ter Schritt: (rn-3, rn-2) rn-3 ÷ rn-2 = qn-1 rn-2 + rn-1 rn-1 = rn-3 - qn-1 rn-2
n-ter Schritt: (rn-2, rn-1) rn-2 ÷ rn-1 = qn rn-1 + rn, mit rn = 0 rn = 0: Abbruch

Tabelle 1: Der erweiterte Euklidische Algorithmus: Die zweite Spalte zeigt das Zahlenpaar, das in jedem Schritt durcheinander geteilt wird (Ganzzahl-Division). Anschließend wird das Zahlenpaar neu gesetzt: die erste Komponente wird entfernt, an dessen Stelle tritt die zweite Komponente. Die neue zweite Komponente ist der Rest, der sich bei der Division ergeben hat. Die Iteration wird so lange fortgeführt bis der Rest gleich null ist.

Ergebnis:

gcd(a, b) = rn-1

Die Gleichungen aus den letzten Spalte können jetzt von unten nach oben ineinander eingesetzt werden (beginnend mit rn-1 = rn-3 - qn-1 rn-2). Dabei sind die Reste rn-2, ..., r1 als Unbekannte aufzufassen, die sukzessive eliminiert werden. Am Ende wird rn-1 als Linearkombination von a und b dargestellt. Die folgenden Beispiele demonstrieren dies.

Beispiele:

1. Beispiel: a = 24 und b = 18

1. Schritt: (a, b) = (24, 18) 24 ÷ 18 = 1 Rest 6 6 = 24 - 18
2. Schritt: (18, 6) 18 ÷ 6 = 3 Rest 0 r2 = 0: Abbruch

Tabelle 2: Der erweiterte Euklidische Algorithmus für a = 24 und b = 18.

Ergebnis:

gcd(a = 24, b = 18) = 6

6 = 24 - 18

Dieses erste Beispiel kann eigentlich nur die Berechnung des größten gemeinsamen Teilers veranschaulichen; seine Berechnung als Linearkombination von a und b ist hier zu einfach, um zu verstehen, wie sie im allgemeinen Fall auszuführen ist. Denn die Gleichung, mit der man das "Rückwärts-Einsetzen" beginnt, ist zugleich die letzte Gleichung, die verwendet werden muss. Das folgende kompliziertere Beispiel wird das "Rückwärts-Einsetzen" besser demonstrieren.

2. Beispiel: a = 34 und b = 24

1. Schritt: (a, b) = (34, 24) 34 ÷ 24 = 1 Rest 10 10 = 34 - 24
2. Schritt: (24, 10) 24 ÷ 10 = 2 Rest 4 4 = 24 - 2 · 10
3. Schritt: (10, 4) 10 ÷ 4 = 2 Rest 2 2 = 10 - 2 · 4
4. Schritt: (4, 2) 4 ÷ 2 = 2 Rest 0 r4 = 0: Abbruch

Tabelle 3: Der erweiterte Euklidische Algorithmus für a = 34 und b = 24.

Ergebnis:

gcd(a = 34, b = 24) = 2

Wie sich der größte gemeinsame Teiler als Linearkombination von 34 und 24 darstellen lässt, ergibt sich aus den Gleichungen der letzten Spalte. Man beginnt mit der Gleichung:

2 = 10 - 2 · 4,

die so zu lesen ist:

2 = 10 - 2 · 4 ⇒

2 = 10 - 2 · (24 - 2 · 10) = 3 · 10 - 2 · 24.

Das heißt die Multiplikationen werden nicht ausgeführt, sondern die Reste bleiben stehen. Jetzt ist 2 als Linearkombination von 24 und 10 ausgedrückt

Die nächste zu eliminierende Unbekannte ist 10. Man setzt die Gleichung 10 = 34 - 24 ein:

2 = 3 · 10 - 2 · 24 ⇒

2 = 3 · (34 - 24) - 2 · 24 = 3 · 34 - 5 · 24

Auf der rechten Seite stehen jetzt die Zahlen a = 34 und b = 24 mit den gesuchten Koeffizienten k und l:

2 = 3 · 34 - 5 · 24 = k · 34 + l · 24 ⇒

k = 3, l = -5.

In einfachen Fällen wird man die Koeffizienten erraten können oder wie im Beispiel oben ergeben sie sich nach einer Iteration. Das Verfahren hier kann zur Berechnung von k und l immer angewendet werden.

Aufgabe:

Berechnen Sie den größten gemeinsamen Teiler für a = 34 und b = 3 und stellen Sie ihn als Linearkombination von a und b dar.

♦ ♦ ♦ ♦ ♦

Liest man die Vorgehensweise zur Berechnung des größten gemeinsamen Teilers zweier Zahlen a und b zum ersten Mal und rechnet Beispiele, wird man sich einige Fragen stellen:

  1. Warum liefern diese Anweisungen überhaupt einen gemeinsamen Teiler zweier Zahlen a und b?
  2. Und wenn man dies voraussetzt, warum liefert der Algorithmus ausgerechnet, den größten gemeinsamen Teiler?
  3. Kommt der Algorithmus bei allen Eingabewerten nach endlich vielen Berechnungen zu einem Ende? Kann er nicht in eine Endlos-Schleife laufen?
  4. Kann man die Rechenschritte im Hasse-Diagramm oder in einer anderen geeigneten Darstellung plausibel machen?

Der folgende Satz 3 beschreibt die Eigenschaften des Iterationsverfahrens – er liefert eine Antwort auf die ersten drei Fragen, die letzte Frage wird dann weiter unten diskutiert (siehe geometrische Interpretation in Abbildung 3 und 4):

Satz 3 (erweiterte Euklidischer Algorithmus):

Sind a und b natürliche Zahlen mit a ≥ b. Dann gilt für den oben beschriebenen erweiterten Euklidischen Algorithmus:

  1. Der Algorithmus liefert nach höchstens b Schritten einen Rest null.
  2. Die in jedem Iterationsschritt berechneten Werte für qi und ri sind eindeutig.
  3. Der letzte Rest ungleich null ist der größte gemeinsame Teiler von a und b.
  4. Die bei den Iterationsschritten berechneten Gleichungen für die Reste liefern eine Darstellung für gcd(a, b) als Linearkombination von a und b.

♦ ♦ ♦ ♦ ♦

Dieser Satz soll hier nicht streng bewiesen werden; die Beweisideen werden lediglich zusammengestellt und so formuliert, dass man daraus leicht einen Beweis mit vollständiger Induktion machen kann.

Beweisskizze für Satz 3:

1. Abbruch des Euklidischen Algorithmus:

Der Algorithmus startet mit zwei Zahlen a und b, wobei b kein Teiler von a ist. Daher ist bei der Ganzzahl-Division der Rest r1 eine Zahl 0, 1, 2, ..., b - 1 und somit echt kleiner als b. Ist der Rest gleich null, ist der Algorithmus beendet, andernfalls wird im nächsten Schritt durch diesen Rest r1 geteilt. Das Ergebnis ist somit wieder eine Zahl, die echt kleiner wird, und so weiter. Nach maximal b Schritten kommt der Algorithmus zu einem Ende; dass zwei aufeinander folgende Reste gleich sind, kann nicht vorkommen.

2. Eindeutigkeit der Reste qi und ri.

Sowohl die Startwerte als auch in jedem weiteren Schritt wird eine Ganzzahl-Division durchgeführt, die eindeutige Werte für die qi und ri liefert. Eine Division durch null kann nicht auftreten, da dies die Abbruchbedingung ist.

3. Berechnung des größten gemeinsamen Teilers von a und b:

Sieht man den Euklidischen Algorithmus unter dem Gesichtspunkt, dass er gcd(a, b) berechnen soll, ist dies der entscheidende Teil von Satz 3. Nach Satz 2, Teil 2, weiß man, dass jeder Rest ri in der Iteration alle gemeinsamen Teiler von a und b selber als Teiler besitzt.

Im letzten Iterationsschritt gilt zusätzlich, dass der Rest rn-1 ein Teiler von rn-2 ist. Aber dann kann rn-1 nur mit dem größten der gemeinsamen Teiler gcd(a, b) übereinstimmen; denn wäre er kleiner, könnte er nicht gcd(a, b) als Teiler besitzen.

4. Darstellung von gcd(a, b) als Linearkombination von a und b:

Für einen Beweis durch vollständige Induktion wird man nicht in der Reihenfolge vorgehen wie in den Beispielen oben, wo die Gleichungen für die Reste von unten nach oben ineinander eingesetzt wurden.

Die erste Gleichung (für r1) zeigt auf der rechten Seite eine Linearkombination von a und b. Setzt man r1 in die zweite Gleichung (für r2) ein, erhält man r2 als Linearkombination von a und b. Dies kann man bis zum Abbruch des Algorithmus so fortsetzen. Die letzte derartige Gleichung stellt dann rn-1 = gcd(a, b) als Linearkombination von a und b dar.

Charakterisierung der Linearkombinationen zweier Zahlen

Nachdem jetzt ausführlich der Euklidische Algorithmus besprochen wurde, kann man endlich zur Ausgangsfrage zurückkehren: Wie lassen sich die Linearkombinationen zweier ganzer Zahlen a und b charakterisieren?

Die wichtigsten Eigenschaften der Menge LK(a, b) waren in den Aussagen 4 und 5 von Satz 1 bereits enthalten; mit Hilfe des größten gemeinsamen Teilers lassen sie sich treffender formulieren:

Die Menge LK(a, b) stimmt mit den Vielfachen von gcd(a, b) überein. Oder um die Kongruenz und die Restklassen heranzuziehen: Die Menge LK(a, b) ist gleich der Restklasse R[0] (mod gcd(a, b)).

Satz 4 (Charakterisierung der Linearkombinationen von a und b):

Sind a, b ∈ N und LK(a, b) die Menge der Linearkombinationen von a und b, dann gilt:

LK(a, b) = R[0] (mod gcd(a, b)).

Beweis:

Zu zeigen sind also zwei Inklusionen ⊆ und ⊇

Die Inklusion ⊆: Ist x eine Linearkombination von a und b, dann ist nach Satz 1, Punkt 4, gcd(a, b) ein Teiler x. Aber das heißt es gibt ein ganzzahliges n mit x = n · gcd(a, b). Daher ist x ∈ R[0] (mod gcd(a, b)).

Die Inklusion ⊇: Ist x ∈ R[0] (mod gcd(a, b)), dann gibt es ein ganzzahliges n mit x = n · gcd(a, b). Nach Satz 3, Punkt 3, lässt sich gcd(a, b) als Linearkombination von a und b darstellen, dann aber auch das Vielfache n · gcd(a, b).

Folgerung: Die Zahl gcd(a, b) ist die kleinste natürliche Zahl, die in LK(a, b) enthalten ist.

Nach Satz 4 gibt es hier nichts zu beweisen: Denn die Restklasse R[0] (mod gcd(a, b)) enthält alle ganzzahligen Vielfachen von gcd(a, b), aber keine natürliche Zahl zwischen 0 und gcd(a, b).

Diskussion des Euklidischen Algorithmus

Varianten des Euklidischen Algorithmus

Euklidischer Algorithmus und Primfaktorzerlegung

Oben wurden Beispiele angeführt, bei denen mit Hilfe des Euklidischen Algorithmus der größte gemeinsame Teiler zweier Zahlen, etwa a = 24 und b = 18, berechnet wird. Mancher Leser wird sich dabei gefragt haben: Wozu der Aufwand? Wenn man die alle Teiler von 24 und 18 durchprobiert, hat man schnell gcd(24, 18) = 6 gefunden.

Und wenn die Zahlen etwas komplizierter sind, gibt es einfaches Verfahren:

Diese beiden Verfahren – "Teiler durchprobieren" und "Primfaktorzerlegung" – mögen bei kleinen Zahlen sehr viel einfacher und schneller sein als der Euklidische Algorithmus. Bei großen Zahlen, etwa solche, die nicht mehr mit dem Taschenrechner verarbeitet werden können, sind diese Verfahren dem Euklidischen Algorithmus deutlich unterlegen.

Der Euklidische Algorithmus und seine Erweiterung

Der Algorithmus, der oben ausführlich vorgestellt wurde, heißt erweiterter Euklidischer Algorithmus (siehe Tabelle 1). Als Euklidischer Algorithmus wird die Vorgehensweise bezeichnet, wenn die Berechnungen aus der 4. Spalte in Tabelle 1 nicht ausgeführt werden.

Man beachte, dass die Umformung, die von der dritten Spalte zur vierten Spalte führt, für die Berechnung des größten gemeinsamen Teilers von a und b nicht notwendig ist. Der Rest, der in das Zahlenpaar der zweiten Spalte eingesetzt wird und an dem man erkennt, ob der Algorithmus abbricht, kann schon aus der dritten Spalte abgelesen werden.

Man kann es daher auch so formulieren:

  1. Der Euklidische Algorithmus hat das Ziel gcd(a, b) zu berechnen.
  2. Der erweiterte Euklidische Algorithmus hat zwei Ziele:

Wenn man nur an der Berechnung des gcd(a, b) interessiert ist, wird man den Euklidischen Algorithmus zuerst besprechen. Hier wurde sofort der erweiterte Euklidische Algorithmus vorgestellt, da die Fragestellung nach der Charakterisierung der Menge der Linearkombinationen zweier Zahlen vorangestellt wurde.

Der Blankinship-Algorithmus

Möchte man den Euklidischen Algorithmus so implementieren, wie er oben vorgestellt wurde, steht man vor einem Problem: Die Berechnung der Koeffizienten k und l, mit denen gcd(a, b) als Linearkombination von a und b dargestellt werden, werden rückwärts berechnet. Das heißt man müsste alle q-Werte abspeichern, die in den Iterationsschritten erzeugt werden, und beim "Rückwärts-Einsetzen" verwenden.

Unten in den R-Skripten wird der Algorithmus von Blankinship vorgestellt, der dieses Problem elegant löst und es ermöglicht, die Koeffizienten k und l vorwärts zu berechnen, also gleichzeitig mit der Iteration, die die Ganzzahl-Divisionen bis zur Abbruchbedingung durchführt.

Geometrische Interpretation

Der Euklidische Algorithmus kann geometrisch interpretiert werden. Dazu wird aus den gegebenen Zahlen a und b ein Rechteck gebildet. Der größte gemeinsame Teiler gcd(a, b) ist gerade diejenige Seitenlänge eines Quadrates mit folgenden Eigenschaften:

Dabei ist mit vollständiger Parkettierung gemeint, dass das Rechteck lückenlos mit den Quadraten ausgelegt werden kann.

Abbildung 3: Parkettierung eines Rechtecks mit Seitenlängen a = 24 und b = 18. Mit jedem gemeinsamen Teiler von a und b kann ein Quadrat gebildet werden, das das Rechteck vollständig parkettiert. Unten sind die Parkettierungen mit Quadraten der Seitenlängen D = 6 und d = 3 gezeigt. Man könnte auch d = 2 und d = 1 für eine vollständige Parkettierung verwenden (nicht dargestellt). Sucht man das größte Quadrat für die Parkettierung, muss man den größten gemeinsamen Teiler von a = 24 und b = 18 wählen, hier D = 6. Verwendet man ein noch größeres Quadrat, kann man das Rechteck entweder nicht vollständig ausfüllen oder man wird eine zu große Fläche bedecken.Abbildung 3: Parkettierung eines Rechtecks mit Seitenlängen a = 24 und b = 18. Mit jedem gemeinsamen Teiler von a und b kann ein Quadrat gebildet werden, das das Rechteck vollständig parkettiert. Unten sind die Parkettierungen mit Quadraten der Seitenlängen D = 6 und d = 3 gezeigt. Man könnte auch d = 2 und d = 1 für eine vollständige Parkettierung verwenden (nicht dargestellt). Sucht man das größte Quadrat für die Parkettierung, muss man den größten gemeinsamen Teiler von a = 24 und b = 18 wählen, hier D = 6. Verwendet man ein noch größeres Quadrat, kann man das Rechteck entweder nicht vollständig ausfüllen oder man wird eine zu große Fläche bedecken.

Mit dieser geometrischen Interpretation von gcd(a, b) kann man sich auch leicht die Vorgehensweise beim Euklidischen Algorithmus veranschaulichen: Wie geht man vor, um zu einem gegebenen Rechteck (mit Seitenlängen a und b) das Quadrat für eine vollständige Parkettierung zu bestimmen? Dies ist in Abbildung 4 dargestellt.

Abbildung 4: Vorgehensweise beim Euklidischen Algorithmus. Man versucht die kürzere Rechteckseite b = 18 in die längere Seite a = 24 einzupassen. Überflüssige Vielfache von b fallen weg, mit dem Rest r wird das neue Rechteck gebildet (Seitenlängen b und r). Dies definiert ein Iterationsverfahren, das abbricht, wenn die kürzere Seite Teiler der längeren Seite ist; die Abbruchbedingung wird hier schon nach dem zweiten Schritt erreicht.Abbildung 4: Vorgehensweise beim Euklidischen Algorithmus. Man versucht die kürzere Rechteckseite b = 18 in die längere Seite a = 24 einzupassen. Überflüssige Vielfache von b fallen weg, mit dem Rest r wird das neue Rechteck gebildet (Seitenlängen b und r). Dies definiert ein Iterationsverfahren, das abbricht, wenn die kürzere Seite Teiler der längeren Seite ist; die Abbruchbedingung wird hier schon nach dem zweiten Schritt erreicht.

Als Algorithmus würde man das Vorgehen jetzt etwa so formulieren:

An dieser Beschreibung des Euklidischen Algorithmus ist besser zu erkennen, welche Bedeutung q in der Ganzzahl-Division hat:

a ÷ b = q · b + r ⇒ r = a - q · b.

Der Teiler q gibt an, wie oft die kürzere Seite in die längere Rechteckseite passt. Dieser Faktor q spielt aber für die weitere Berechnung keine Rolle – er steht gerade für den Teil des Rechtecks, den man wegschneiden kann.

Man erkennt in Abbildung 4 insbesondere die beiden Möglichkeiten, die bei einer Division bestehen:

Dabei wird meist der erste Fall mehrmals auftreten, was zu einem echten Iterationsverfahren führt.

Aufgabe: Stellen Sie den Euklidischen Algorithmus zu a = 34 und b = 24 analog zu Abbildung 4 dar.

♦ ♦ ♦ ♦ ♦

Möchte man nur den größten gemeinsamen Teiler geometrisch interpretieren, kann man auch von Abbildung 2 ausgehen: Sind zwei Maßstäbe der Länge a und b mit a > b gegeben, so kann man sich fragen, welches der kleinste Abstand d ist, den man als Linearkombination von a und b darstellen kann. Linearkombination bedeutet hier so viel wie "beliebiges Aneinanderlegen der beiden Maßstäbe"

Klar ist, dass man den Abstand a - b erzeugen kann. Nicht sofort klar ist, ob die Differenz a - b zugleich der kleinste Abstand ist, den man mit den Maßstäben erzeugen kann. Die obigen Beispiele haben gezeigt:

  1. Für a = 24 und b = 18 stimmen gcd(a, b) und a - b überein und a - b = 6 ist tatsächlich der kleinste mögliche Abstand.
  2. Für a = 34 und b = 24 stimmen gcd(a, b) und a - b nicht überein. Durch eine geschickte Wahl von k und l in ka + lb = 5 · 34 - 7 · 24 = 2 erhält man einen Abstand, der kleiner ist als a - b. Da a und b beide gerade sind, kann man keinen noch kleineren Abstand herstellen.

Den Euklidischen Algorithmus kann man in dieser Sichtweise nur schwer interpretieren. In den R-Skripten wird dann ein weiterer Algorithmus vorgestellt, mit dem man den größten gemeinsamen Teiler berechnen kann, nämlich der Algorithmus von Stein. Dessen Vorgehensweise kann leicht mit Abbildung 2 in Verbindung gebracht werden: Man sucht zu zwei gegebenen Längen a und b eine einzige Länge d, so dass die Vielfachen von d gerade die Linearkombinationen von a und b sind. Der Algorithmus von Stein endet, wenn – in einem gewissen Sinne – diese einzige Länge d gefunden ist.

Eigenschaften des größten gemeinsamen Teilers gcd(a, b)

Die bisherigen Diskussionen des größten gemeinsamen Teilers gcd(a, b) für ganze Zahlen a, b haben gezeigt, dass man eigentlich nur positive Zahlen a und b benötigt und selbst wenn a oder b negativ sind, reicht meist die Kenntnis der positiven Teiler der Zahlen aus. Insbesondere die geometrische Interpretation von gcd(a, b) und des Euklidischen Algorithmus haben dies verdeutlicht.

Die Formulierung der Eigenschaften des größten gemeinsamen Teilers wird sehr umständlich, wenn man gcd(a, b) auf Z × Z definiert. In den folgenden Abschnitten wird daher gcd(a, b) nur auf N × N betrachtet.

Definitionen

Anders als im Kapitel über die Linearkombinationen in Z wird der größte gemeinsame Teiler jetzt für natürliche Zahlen definiert.

Definition: Sind a, b ∈ N, dann wird jede Zahl d mit d|a und d|b als gemeinsamer Teiler von a und b bezeichnet. Das Maximum dieser Teiler d wird als der größte gemeinsame Teiler von a und b bezeichnet und mit gcd(a, b) abgekürzt.

Bemerkungen:

  1. Da jede natürliche Zahl den Teiler 1 hat, ist die Menge der gemeinsamen Teiler zweier Zahlen niemals leer.
  2. Und da jede Zahl maximal endlich viele Teiler hat, existiert der größte gemeinsame Teiler und ist eindeutig definiert.
  3. Aus den beiden Punkten folgt sofort: gcd(a, b) ≥ 1 für a, b ∈ N.
  4. Die oben mit Worten formulierte Definition von gcd(a, b) würde man symbolisch schreiben als:

a, b ∈ N ⇒ gcd(a, b) = max{d : d|a und d|b}.

Besonders wichtig ist der Spezialfall, wenn der (triviale) Teiler d = 1 der einzige gemeinsame Teiler zweier Zahlen a und b ist.

Definition: Zwei natürliche Zahlen a und b werden als teilerfremd bezeichnet, wenn gcd(a, b) = 1.

Aufgaben:

  1. Wie viele Zahlen b zwischen 1 und 24 gibt es, die zu a = 6 teilerfremd sind? Sind all diese Zahlen b Primzahlen?
  2. Wie lauten die Antworten auf die letzte Frage für a = 44?
  3. Wie müsste man obige Definitionen abändern, wenn man jeweils a, b ∈ Z zulässt?

Eigenschaften von gcd(a, b)

Die meisten Eigenschaften des größten gemeinsamen Teilers wurden in den Abschnitten oben bereits – ausdrücklich oder nur zwischen den Zeilen – formuliert und verwendet. Wegen ihrer Wichtigkeit sollen sie nochmals als Sätze formuliert und (teilweise) bewiesen werden.

Satz 6:

Für a, b, c, n, m ∈ N gilt:

(1) gcd(a, a) = a.

(2) Ist b|a, dann ist gcd(a, b) = b. Ist umgekehrt gcd(a, b) = b, dann muss b|a gelten.

(3) gcd(a, b) = gcd(b, a).

(4) Ist c|a und c|b, dann ist auch c|gcd(a, b).

(5) gcd(a, b) = gcd(a, b + n · a) und speziell gcd(a, b) = gcd(a, a + b) = gcd(a, a - b).

(6) gcd(c · a, c · b) = c · gcd(a, b).

(7) gcd(a, b) = 1 und gcd(a, c) = 1 ⇒ gcd(a, b · c) = 1.

Bemerkungen:

  1. Die Aussage (5) sollte man besser mit a, b, n ∈ Z formulieren.
  2. Aussage (5) ist auch die zentrale Aussage, die beim Euklidischen Algorithmus eingesetzt wird, wenn man von gcd(a, b) = gcd(b, r) verwendet für a = q · b + r. Dies ist leichter zu sehen, wenn man schreibt: gcd(b, r) = gcd(b, r + q · b) = gcd(b, a). Im Vergleich zu (5) sind jetzt nur die Bezeichnungen anders gewählt.

Beweisideen für Satz 6:

Die Punkte (1) bis (4) folgen sofort aus der Definition von gcd(a, b).

Beweisidee zu (5): Um etwa gcd(a, b) = gcd(a, a - b) zu beweisen, zeigt man, dass die Menge aller gemeinsamen Teiler von a und b sowie von a - b identisch sind, also

{d ∈ N : d|a und d|b} = {d ∈ N : d|a und d|(a - b)}.

Und wenn die Mengen identisch sind, besitzen sie ein identisches Maximum.

Mit den selben Argumenten kann man dann gcd(a, b) = gcd(a, a + b) beweisen und durch Iteration die allgemeine Aussage gcd(a, b) = gcd(a, b + n · a).

Beweisidee zu (6): Ähnlich wie in (5) vergleicht man hier die Menge der gemeinsamen Teiler von a und b beziehungsweise von c · a und c · b.

Beweisidee zu (7): Man nimmt an, dass es einen gemeinsamen Teiler d ( mit d > 1) zu a und b · c gibt und zeigt, dass dann d

Darstellung der Funktion gcd(a, b)

Es ist klar, dass man gcd(a, b) als eine Funktion zweier Variabler interpretieren kann. Aber dann möchte man diese auch graphisch darstellen und erhofft sich davon eine tiefere Einsicht in die Bedeutung der Funktion und ihrer Eigenschaften.

Die folgende Abbildung 5 stellt gcd(a, b) dar, genauer:

  1. Für a und b werden die natürlichen Zahlen 1, 2, ..., 130 eingesetzt. Der Definitionsbereich liegt in der Zeichenebene.
  2. Da man die dritte Dimension nur schwer veranschaulichen kann und die Funktion schnell ihre Werte ändert, werden Funktionswerte durch Farben dargestellt:

Abbildung 5: Graphische Darstellung des größten gemeinsamen Teilers, also der Funktion gcd(a, b) für a, b = 1, 2, ..., 130. Weitere Erklärung im Text.Abbildung 5: Graphische Darstellung des größten gemeinsamen Teilers, also der Funktion gcd(a, b) für a, b = 1, 2, ..., 130. Weitere Erklärung im Text.

Man erkennt in Abbildung 5:

Außer den genannte Eigenschaften fällt es schwer, aus Abbildung 5 weitere Informationen abzulesen. Dazu hilft der folgende Zugang:

Aufgabe:

Versuchen Sie zu formulieren, welche "Ähnlichkeit" zwischen den Abbildungen bestehen muss.

Abbildung 6: Darstellung der teilerfremden Punkte (a, b) für a, b = 1, 2, ..., 130.Abbildung 6: Darstellung der teilerfremden Punkte (a, b) für a, b = 1, 2, ..., 130.

Abbildung 7: Darstellung der Punkte (a, b) mit gcd(a, b) = 2, für a, b = 1, 2, ..., 130 (rot). Zusätzlich sind die Punkte mit a = 1 oder b = 1 gezeigt (blau).Abbildung 7: Darstellung der Punkte (a, b) mit gcd(a, b) = 2, für a, b = 1, 2, ..., 130 (rot). Zusätzlich sind die Punkte mit a = 1 oder b = 1 gezeigt (blau).

Die "Ähnlichkeit" zwischen den Abbildungen 6 und 7 kann man mit Aussage (6) aus Satz 6 erklären: Abbildung 6 zeigt die Menge der teilerfremden Zahlenpaare (a, b). Werden beide Zahlen mit 2 multipliziert, so haben (2a, 2b) offensichtlich nur den Faktor 2 gemeinsam; aber dann gilt gcd(2a, 2b) = 2.

Umgekehrt muss sich jedes Zahlenpaar mit größtem gemeinsamen Teiler gleich 2 auf diese Weise aus einem teilerfremden Zahlenpaar erzeugen lassen. Das heißt aber, dass jeder Punkt aus Abbildung 6 um den Faktor 2 gestreckt (sowohl in a- als auch in b-Richtung) einen Punkt in Abbildung 7 ergibt.

In Abbildung 8 sind alle Punkte aus Abbildung 6 und 7 gleichzeitig dargestellt: die Ähnlichkeit der Punktmengen ist dann aber nicht mehr so leicht zu sehen wie im direkten Vergleich der Abbildungen 6 und 7.

Wenn man also verstehen möchte, wie die Funktion gcd(a, b) "aussieht", muss man nur verstehen, wie die Menge der teilerfremden Punkte in der a-b-Ebene aussieht. Die anderen Funktionswerte erhält man durch Streckungen über die Aussage (6) aus Satz 6.

Abbildung 8: Darstellung sowohl der teilerfremden Punkte (a, b) als der Punkte mit gcd(a, b) = 2, für a, b = 1, 2, ..., 130. (Anstelle der blauen Farbe in Abbildung 6 wurde für die teilerfremden eine weniger kräftige Farbe gewählt, damit die roten Punkte (gcd(a, b) = 2) deutlicher zu sehen sind.Abbildung 8: Darstellung sowohl der teilerfremden Punkte (a, b) als der Punkte mit gcd(a, b) = 2, für a, b = 1, 2, ..., 130. (Anstelle der blauen Farbe in Abbildung 6 wurde für die teilerfremden eine weniger kräftige Farbe gewählt, damit die roten Punkte (gcd(a, b) = 2) deutlicher zu sehen sind.

R-Skripte

Warnung vor negativen Resten

In den folgenden Abschnitten sollen natürlich Algorithmen zur Berechnung des größten gemeinsamen Teilers entwickelt werden. Da diese auf der Ganzzahl-Division und der Berechnung des Restes beruhen, muss man eine Warnung aussprechen: In der Mathematik kann bei einer Division durch eine ganze Zahl k der Rest nur einen der Werte r = 0, 1, ..., k - 1 annehmen. Und alle Varianten des Euklidischen Algorithmus, die oben besprochen wurden, beruhen auf dieser Konvention.

Diese Konvention erscheint so selbstverständlich, dass man leicht vergisst, welche Falle sie enthält: Welche Werte nimmt der Rest an, wenn in a ÷ b ein Eingabewert (oder beide Eingabewerte) negativ ist?

Es ist klar, dass

20 ÷ 6 = 3 Rest 2.

Aber welche Ergebnisse liefern

(-20) ÷ 6 oder 20 ÷ (-6) oder (-20) ÷ (-6)?

Die Ganzzahl-Division ist in verschiedenen Programmiersprachen unterschiedlich implementiert und daher sollte man – bevor man einen Algorithmus wie de Euklidischen Algorithmus implementiert – testen, welche Ergebnisse diese Berechnungen liefern.

Das folgende Skript zeigt die Ergebnisse in R:

# Test der Ganzzahl-Division:

20 %/% 6        # 3
20 %% 6         # 2


-20 %/% 6       # -4
-20 %% 6        # 4

20 %/% -6       # -4
20 %% -6        # -4

-20 %/% 6       # 3
-20 %% 6        # -2

Der Algorithmus von Euklid zur Berechnung des größten gemeinsamen Teilers

Wenn man den Euklidischen Algorithmus in ein Programm umsetzt, muss man sich zuvor fragen, was das Programm später einmal leisten soll; oben wurden zwei Varianten des Euklidischen Algorithmus besprochen, je nachdem wie er später eingesetzt werden soll, hat man mehrere Möglichkeiten den Algorithmus umzusetzen. Man sollte daher folgende Fragen klären:

Diese Fragen deuten darauf hin, dass selbst die einfache Fragestellung nach der Berechnung des größten gemeinsamen Teilers zu einer Vielzahl von Algorithmen führt. In den folgenden Unterabschnitten sollen einige Algorithmen vorgestellt werden:

  1. Das Arbeitstier für die Berechnung von gcd(a, b), nämlich ein möglichst einfacher Algorithmus, der nur gcd(a, b) berechnet, keine weiteren Ausgaben liefert und voraussetzt, dass die Eingabewerte der Konvention a ≥ b > 0 gehorchen. Die letzte Bedingung sorgt für einen schlanken Algorithmus.
  2. Das Arbeitstier mit debug-Ausgaben: obiger Algorithmus wird zum Testen so erweitert, dass er geeignete Konsolen-Ausgaben erzeugt (die sich leicht wieder abschalten lassen).
  3. Eine Wrapper-Funktion für das Arbeitstier: Eine Funktion, die die Eingabewerte prüft und anschließend das Arbeitstier gemäß der Konventionen anspricht.
  4. Der erweiterte Euklidische Algorithmus, der gcd(a, b) sowie die beiden Koeffizienten k und l (für gcd(a, b) = ka + lb) berechnet. Dieser Algorithmus wird hier in der Variante von Blankinship implementiert, der die Berechnung der Koeffizienten gegenüber der Darstellung in Tabelle 1 deutlich vereinfacht. Auch dieser Algorithmus wird so implementiert, dass man Debug-Informationen über alle Zwischenergebnisse abfragen kann.
  5. Im letzten Abschnitt wird der Algorithmus von Stein implementiert, der zum Euklidischen Algorithmus äquivalent ist, aber völlig andere Rechenschritte einsetzt.

Das Arbeitstier für gcd(a, b)

Oben wurde die Warnung ausgesprochen, wonach die Ganzzahl-Division nicht die gewünschten Ergebnisse liefert, die man für den Euklidischen Algorithmus benötigt. Daher wird eine Funktion gcd.conv(a, b) implementiert, die die Berechnung des größten gemeinsamen Teilers ausführt, wobei die Eingabewerte gewissen Konventionen gehorchen müssen. Die Verantwortlichkeit dafür, dass diese Konventionen eingehalten werden, wird an die Wrapper-Funktion gcd(a, b) übertragen.

Die Konventionen für a, b lauten – sie entsprechen genau der Vorgehensweise in Tabelle 1:

Die Implementierung ist als rekursive Funktion realisiert. Wer mit rekursiven Funktionen nicht vertraut ist, kann im Kapitel Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem im Abschnitt Umwandlung einer Dezimalzahl in eine Dualzahl mit der Funktion decToBin(n) eine ausführliche Diskussion finden, wie die Befehle einer Funktion abgearbeitet werden, die sich selbst aufruft.

Die Funktion gcd.conv(a, b) besitzt eine ganz ähnliche Struktur (siehe folgendes Skript):

gcd.conv <- function(a, b){
  if(b == 0){
    return(a)
  }
  else{
    r <- a %% b
    return(gcd.conv(b, r))
  }
}

Die Rekursion beim Euklidischen Algorithmus soll die folgende Abbildung 9 anschaulich machen.

Abbildung 9: Rekursive Berechnung des größten gemeinsamen Teilers. Es soll gcd(a, b) berechnet werden, dazu wird a in der Form a = qb + r dargestellt, wobei der Faktor q und der Rest r ganze Zahlen sind und r = 0, 1, 2, ..., b - 1 sein kann. Durch die Darstellung a = qb + r sind b und r eindeutig festgelegt (in der Abbildung ist q = 3). Wegen der Gleichheit gcd(a, b) = gcd(b, r) wird im nächsten Schritt gcd(b, r) berechnet. Dieses Verfahren wird so lange fortgesetzt, bis der Rest gleich 0 ist. Wenn gcd(b, 0) zu berechnen ist, ist b der größte gemeinsame Teiler.Abbildung 9: Rekursive Berechnung des größten gemeinsamen Teilers. Es soll gcd(a, b) berechnet werden, dazu wird a in der Form a = qb + r dargestellt, wobei der Faktor q und der Rest r ganze Zahlen sind und r = 0, 1, 2, ..., b - 1 sein kann. Durch die Darstellung a = qb + r sind b und r eindeutig festgelegt (in der Abbildung ist q = 3). Wegen der Gleichheit gcd(a, b) = gcd(b, r) wird im nächsten Schritt gcd(b, r) berechnet. Dieses Verfahren wird so lange fortgesetzt, bis der Rest gleich 0 ist. Wenn gcd(b, 0) zu berechnen ist, ist b der größte gemeinsame Teiler.

Bevor der Einsatz dieser Funktion gezeigt wird, wird sie mit Ausgaben versehen, um die Rechenschritte leichter nachzuvollziehen.

Das Arbeitstier für gcd(a, b) mit debug-Ausgaben

Möchte man erst einmal den Euklidischen Algorithmus verstehen, ist es hilfreich Zwischenergebnisse ausgeben zu lassen. Das folgende Skript zeigt eine Version der oben vorgestellten Funktion gcd.conv(a, b) mit zusätzlichen Ausgaben, die sich leicht abschalten lassen (per default sind sie abgeschaltet):

gcd.conv <- function(a, b, debug = FALSE){
  if(b == 0){
    return(a)
  }
  else{
    r <- a %% b
    if(debug){
      cat("a = ", a, " | b = ", b, " || a/b =", a %/% b, " Rest ", r, " || Produkt a*b: ", a * b, "\n")
    }
    return(gcd.conv(b, r, debug = debug))
  }
}

Neu ist jetzt:

Beispiele:

1. a = 24 und b = 18:

gcd.conv(a = 24, b = 18, debug =  TRUE)
# a =  24  | b =  18  || a/b = 1  Rest  6  || Produkt a*b:  432 
# a =  18  | b =  6  || a/b = 3  Rest  0  || Produkt a*b:  108 
# [1] 6

Zeile 1: Aufruf der Funktion gcd.conv() mit Ausgaben.

Zeile 2 und 3: Ausgaben während der Berechnung des größten gemeinsamen Teilers:

Zeile 4: Der Rückgabewert der Funktion gcd.conv() wird ausgegeben (an der [1] ist zu erkennen, dass es sich nicht mehr um eine Ausgabe des cat()-Befehls handelt). Der letzte Eingabewert b ist zugleich der größte gemeinsame Teiler von a = 24 und b = 18.

Man vergleiche die Ausgaben mit Tabelle 2 oben.

2. a = 34 und b = 24:

gcd.conv(a = 34, b = 24, debug = TRUE)
# a =  34  | b =  24  || a/b = 1  Rest  10  || Produkt a*b:  816 
# a =  24  | b =  10  || a/b = 2  Rest  4  || Produkt a*b:  240 
# a =  10  | b =  4  || a/b = 2  Rest  2  || Produkt a*b:  40 
# a =  4  | b =  2  || a/b = 2  Rest  0  || Produkt a*b:  8 
# [1] 2

Man vergleiche die Ausgaben mit Tabelle 3 oben.

Die bisherigen Beispiele sind so einfach, dass man den größten gemeinsamen Teiler leicht durch Ausprobieren erraten kann.

3. a = 123 456 und b = 60 060:

gcd.conv(a = 123456, b = 60060, debug = TRUE)
# a =  123456  | b =  60060  || a/b = 2  Rest  3336  || Produkt a*b:  7414767360 
# a =  60060  | b =  3336  || a/b = 18  Rest  12  || Produkt a*b:  200360160 
# a =  3336  | b =  12  || a/b = 278  Rest  0  || Produkt a*b:  40032 
# [1] 12

Mit Hilfe der Ausgaben fällt es jetzt leichter zu untersuchen, welche Fehler auftreten, wenn die Eingabewerte nicht der Konvention gehorchen, die oben formuliert wurde. Diese Fälle müssen dann durch die Wrapper-Funktion abgefangen werden.

Man kann jetzt folgende Verstöße gegen die Konvention für den Aufruf von gcd.conv() testen – mit den Skripten, die zur Warnung cor negativen Resten gezeigt wurden, kann man schon vorhersagen, wann sich ein falsches Ergebnis für den größten gemeinsamen Teiler ergibt.

  1. Das zweite Argument ist größer als das erste Argument: b > a.
  2. Eines der Argumente oder beide Argumente gleich null: a = 0 oder b = 0.
  3. Eines der Argumente oder beide Argumente sind negativ: a < 0 oder b < 0.

Die folgenden drei Skripte zeigen die Tests:

gcd.conv(a = 4, b = 6, debug = TRUE)
# a =  4  | b =  6  || a/b = 0  Rest  4  || Produkt a*b:  24 
# a =  6  | b =  4  || a/b = 1  Rest  2  || Produkt a*b:  24 
# a =  4  | b =  2  || a/b = 2  Rest  0  || Produkt a*b:  8 
# [1] 2

gcd.conv(a = 4, b = 0, debug = TRUE)
# [1] 4

gcd.conv(a = 0, b = 6, debug = TRUE)
# a =  0  | b =  6  || a/b = 0  Rest  0  || Produkt a*b:  0 
# [1] 6

gcd.conv(a = 0, b = 0, debug = TRUE)
# [1] 0

gcd.conv(a = -4, b = 6, debug = TRUE)
# a =  -4  | b =  6  || a/b = -1  Rest  2  || Produkt a*b:  -24 
# a =  6  | b =  2  || a/b = 3  Rest  0  || Produkt a*b:  12 
# [1] 2

gcd.conv(a = 4, b = -6, debug = TRUE)
# a =  4  | b =  -6  || a/b = -1  Rest  -2  || Produkt a*b:  -24 
# a =  -6  | b =  -2  || a/b = 3  Rest  0  || Produkt a*b:  12 
# [1] -2

gcd.conv(a = -4, b = -6, debug = TRUE)
# a =  -4  | b =  -6  || a/b = 0  Rest  -4  || Produkt a*b:  24 
# a =  -6  | b =  -4  || a/b = 1  Rest  -2  || Produkt a*b:  24 
# a =  -4  | b =  -2  || a/b = 2  Rest  0  || Produkt a*b:  8 
# [1] -2

Man erkennt für die drei Fälle:

  1. b > a führt zum richtigen Ergebnis.
  2. Die Berechnung ist richtig, aber unnötig: man kann sie leichter mit einem if else ausführen.
  3. Nur bei negativem b erhält man falsche Ergebnisse.

Die Wrapper-Funktion für gcd.conv() soll jetzt diese Ausnahmefälle abfangen, falls möglich sofort das richtige Ergebnis zurückgeben beziehungsweise geeignete Argumente an die Funktion gcd.conv() weiterreichen.

Die Wrapper-Funktion zur Berechnung des größten gemeinsamen Teilers

Damit man prüfen kann, ob die Eingabewerte an die Wrapper-Funktion tatsächlich ganzzahlig sind, wird die Funktion is.wholenumber(x, tol = .Machine$double.eps^0.5) verwendet; sie ist in der R-Dokumentation zu integer enthalten. Dort wird ausdrücklich darauf hingewiesen, dass man mit is.integer(x) nicht prüfen kann, ob x ganzzahlig ist.

is.wholenumber <- function(x, tol = .Machine$double.eps^0.5){
  # print(tol)    #[1] 1.490116e-08
  return( abs(x - round(x)) < tol )
}

Die folgende Funktion gcd() ist – zugegeben – sehr aufgebläht und versucht allen Eventualitäten gerecht zu werden; je nachdem, wie die Funktion später eingesetzt werden soll, kann man auf einige Spezialfälle verzichten oder sie anders implementieren. Speziell die Fälle mit negativen Eingabewerten oder Eingabewerten gleich null wird man vielleicht anders behandeln wollen.

gcd <- function(a, b, debug = FALSE, tol = .Machine$double.eps^0.5){
  stopifnot(is.wholenumber(x = a, tol = tol))
  stopifnot(is.wholenumber(x = b, tol = tol))
  
  # beide Argumente == 0
  if(a == 0 && b == 0) return(0)
  
  a <- abs(a); b <- abs(b);
  
  # ein Argument == 0
  if(a == 0) return(b)
  if(b == 0) return(a)
  
  # beide Argumente != 0
  
  # a == b
  if(a == b){
    return(a)
  } else {          # a != b
    if(debug){
      cat("Aufruf von gcd.conv() mit a, b: ", a, b, "\n")
    }
    if(a < b){
    return(gcd.conv(a = b, b = a, debug = debug))
    } else {
      return( gcd.conv(a, b, debug) )
    }
  }
}

Die folgenden beiden Skripte zeigen einfache Tests.

gcd(a = 1, b = 1.05)
# Error: is.wholenumber(x = b, tol = tol) is not TRUE

for(i in (-2:2)){
  for(j in (-1:2)){
    cat("i, j: ", i, j, "\n")
    cat("gcd: ", gcd(a = i, b = j, debug = TRUE), "\n\n" )
  }
}
# i, j:  -2 -1 
# Aufruf von gcd.conv() mit a, b:  2 1 
# a =  2  | b =  1  || a/b = 2  Rest  0  || Produkt a*b:  2 
# gcd:  1 
# 
# i, j:  -2 0 
# gcd:  2 
# 
# i, j:  -2 1 
# Aufruf von gcd.conv() mit a, b:  2 1 
# a =  2  | b =  1  || a/b = 2  Rest  0  || Produkt a*b:  2 
# gcd:  1 
# 
# i, j:  -2 2 
# gcd:  2 
# 
# i, j:  -1 -1 
# gcd:  1 
# 
# i, j:  -1 0 
# gcd:  1 
# 
# i, j:  -1 1 
# gcd:  1 
# 
# i, j:  -1 2 
# Aufruf von gcd.conv() mit a, b:  1 2 
# a =  2  | b =  1  || a/b = 2  Rest  0  || Produkt a*b:  2 
# gcd:  1 
# 
# i, j:  0 -1 
# gcd:  1 
# 
# i, j:  0 0 
# gcd:  0 
# 
# i, j:  0 1 
# gcd:  1 
# 
# i, j:  0 2 
# gcd:  2 
# 
# i, j:  1 -1 
# gcd:  1 
# 
# i, j:  1 0 
# gcd:  1 
# 
# i, j:  1 1 
# gcd:  1 
# 
# i, j:  1 2 
# Aufruf von gcd.conv() mit a, b:  1 2 
# a =  2  | b =  1  || a/b = 2  Rest  0  || Produkt a*b:  2 
# gcd:  1 
# 
# i, j:  2 -1 
# Aufruf von gcd.conv() mit a, b:  2 1 
# a =  2  | b =  1  || a/b = 2  Rest  0  || Produkt a*b:  2 
# gcd:  1 
# 
# i, j:  2 0 
# gcd:  2 
# 
# i, j:  2 1 
# Aufruf von gcd.conv() mit a, b:  2 1 
# a =  2  | b =  1  || a/b = 2  Rest  0  || Produkt a*b:  2 
# gcd:  1 
# 
# i, j:  2 2 
# gcd:  2

Man erkennt an den Ausgaben leicht, wann die Berechnung des größten gemeinsamen Teilers schon in der Funktion gcd() stattfindet und wann sie an das Arbeitstier gcd.conv() weitergereicht wird.

Fraglich ist noch der Fall a = 0 und b = 0: Jetzt ist eigentlich jede ganze Zahl Teiler. Um die Konsistenz mit gcd(a, a) = a für a ungleich null zu erreichen, wird der Rückgabewert gleich null gesetzt.

Der erweiterte Euklidische Algorithmus: Verbesserung durch den Blankinship-Algorithmus

Anforderungen an den Algorithmus

Zuletzt soll das Arbeitstier gcd.conv() zum erweiterten Euklidischen Algorithmus blankinship() umgebaut werden. Inwiefern sich der Blankinship-Algorithmus vom oben besprochenen erweiterten Euklidischen Algorithmus unterscheidet, wird im folgenden Unterabschnitt gezeigt (kurz: nur die Berechnung der Koeffizienten k und l erfolgt nicht rückwärts sondern in der Reihenfolge, in der auch die Ganzzahl-Divisionen durchgeführt werden).

An die Funktion blankinship() werden folgende Anforderungen gestellt:

  1. Auf die Spezialfälle, die in der Wrapper-Funktion behandelt werden, soll nicht eingegangen werden, aber die Funktion soll so aufgebaut sein, dass man nachträglich leicht eine Wrapper-Funktion implementieren kann.
  2. Die Eingabewerte a und b sollen wieder der Konvention wie bei gcd.conv() gehorchen.
  3. Es soll wieder der Eingabewert debug = FALSE (default-Wert FALSE) verwendet werden, mit dem sich Debug-Informationen über den gesamten Rechenvorgang abfragen lassen.
  4. Der Rückgabewert von blankinship() soll für debug = FALSE in Vektor mit drei Komponenten sein: gcd(a, b) sowie die beiden Koeffizienten k und l. Für debug = TRUE ist es erforderlich, eine Matrix zurückzugeben, um Zwischenrechnungen über alle Iterationsschritte wie in Tabelle 1 in Der erweiterte Euklidische Algorithmus zu verpacken; dies wird bei der Implementierung von blankinship() ausführlich besprochen.

Der Blankinship-Algorithmus zur Berechnung der Koeffizienten

Wie der Euklidische Algorithmus den größten gemeinsamen Teiler berechnet, sollte inzwischen – nach den Ausführungen im Theorieteil und den Beispielen in den Skripten oben – klar sein. Die zusätzliche Anforderung an den erweiterten Euklidischen Algorithmus, nämlich die Koeffizienten k und l zu berechnen, so dass sich gcd(a, b) als

gcd(a, b) = k · a + l · b

darstellen lässt, ist deutlich schwieriger. Aber für dieses Problem gibt es eine elegante Lösung von Blankinship, bei der gleichzeitig mit der Iteration für den größten gemeinsamen Teiler die Koeffizienten k und l berechnet werden.

Die Arbeitsweise dieses Algorithmus soll in diesem Unterabschnitt und eine Implementierung im nächsten Unterabschnitt vorgestellt werden.

Beim Euklidischen Algorithmus startet man mit den beiden Zahlen (a, b), die in jedem Schritt neu gesetzt werden. Dazu wird jeweils

a ÷ b = q + r oder r = a - q · b

berechnet. Ersetzt wird dann (a, b) durch (b, r). Und dies wird solange wiederholt, bis r = 0.

Die Operation beim Setzen von (a, b) in jedem Iterationsschritt könnte man auch so beschreiben:

Zur Berechnung der Koeffizienten k und l werden jetzt die beiden Einheitsvektoren e1 = (1, 0) und e2 = (0, 1) verwendet. Die drei Vektoren werden als Spaltenvektoren aufgefasst und zu einer 3 × 2 Matrix A0 zusammengefasst (siehe Abbildung 10, Gleichung 1). Die beiden oben beschriebenen Operationen, die mit (a, b) ausgeführt werden, werden auch mit den beiden Vektoren e1 und e2 ausgeführt (siehe Abbildung 10, Gleichung 4). Dies geschieht bei jedem Iterationsschritt des Euklidischen Algorithmus, wodurch Matrizen An entstehen. In den Gleichungen 3 und 4 ist der erste Iterationsschritt dargestellt.

Abbildung 10: Vorgehensweise beim Blankinship-Algorithmus.Abbildung 10: Vorgehensweise beim Blankinship-Algorithmus.

Die beiden Einträge rechts oben in der Matrix An sind gerade die gesuchten Koeffizienten k und l. In Abbildung 10 ist dies für den ersten Iterationsschritt in Gleichung 5 zu sehen.

Die Vorgehensweise soll an den bekannten Beispielen demonstriert werden:

Beispiele:

1. a = 24 und b = 18:

Das Beispiel führt schon nach dem zweiten Iterationsschritt zum Ergebnis. Die Berechnung ist in Abbildung 11 zu sehen.

Abbildung 11: Vorgehensweise beim Blankinship-Algorithmus zur Berechnung des größten gemeinsamen Teilers von a = 24 und b = 18. Gleichung 8 zeigt, wie man die Koeffizienten k und l ablesen kann, um gcd(a, b) als Linearkombination von a und b darzustellen.Abbildung 11: Vorgehensweise beim Blankinship-Algorithmus zur Berechnung des größten gemeinsamen Teilers von a = 24 und b = 18. Gleichung 8 zeigt, wie man die Koeffizienten k und l ablesen kann, um gcd(a, b) als Linearkombination von a und b darzustellen.

Man erkennt auch, dass die Berechnung der Koeffizienten in der zweiten Zeile der Matrix A2 eigentlich überflüssig ist (siehe Gleichung 7 und 8 in Abbildung 11). Denn zur Berechnung der Koeffizienten für gcd(a, b) werden nur die Koeffizienten in der ersten Zeile von A2 benötigt. Da diese wiederum mit den Koeffizienten in der zweiten Zeile von A1 übereinstimmen, ist sogar die gesamte Berechnung von A2 überflüssig. Das heißt sobald sich ein Rest r = 0 ergibt, muss man die nächste Matrix An nicht mehr berechnen.

Man könnte sie lediglich zu Kontrolle verwenden. Denn die Koeffizienten der zweiten Zeile von A2 müssen die 0 erzeugen:

(-3) · 24 + 4 · 18 = 0.

2. a = 34 und b = 24:

Für dieses Beispiel werden hier nur noch die relevanten Matrizen An gezeigt; dem Leser sei empfohlen, die Berechnungen selbständig durchzuführen (siehe Abbildung 12).

Abbildung 12: Matrizen aus dem Blankinship-Algorithmus zur Berechnung des größten gemeinsamen Teilers von a = 34 und b = 24. Es gilt gcd(34, 24) = 2; wie sich 2 als Linearkombination von 34 und 24 darstellen lässt, kann man aus der Matrix A<sub>4</sub> ablesen.Abbildung 12: Matrizen aus dem Blankinship-Algorithmus zur Berechnung des größten gemeinsamen Teilers von a = 34 und b = 24. Es gilt gcd(34, 24) = 2; wie sich 2 als Linearkombination von 34 und 24 darstellen lässt, kann man aus der Matrix A4 ablesen.

Aufgaben:

  1. Bisher wurden lediglich zwei Beispiele gezeigt, an denen sich leicht nachvollziehen lässt, wie man die Koeffizienten berechnet, um gcd(a, b) als Linearkombination von a und b darzustellen. Ein allgemeiner Beweis dafür, dass dieses Verfahren immer richtige Koeffizienten liefert, wurde nicht erbracht. Formulieren Sie die Beweisskizze ähnlich wie zu Satz 3! Welche Aussagen müssen hier zusätzlich zu den Aussagen aus Satz 3 bewiesen werden?
  2. Man kann die Operationen, die beim Blankinship-Algorithmus ausgeführt werden, als Zeilenumformungen einer Matrix interpretieren. Um welche Zeilenumformungen handelt es sich? Formulieren Sie den Algorithmus mit Hilfe von Zeilenumformungen!

Implementierung des Blankinship-Algorithmus

Die Implementierung des oben erläuterten Blankinship-Algorithmus erfolgt in 3 Schritten:

1. Schritt: Es wird eine Funktion nextA() implementiert, die die Matrizen-Operationen ausführt, die in Abbildung 10 gezeigt wurden. Wenn man sie als Zeilenumformungen an einer Matrix interpretiert, benötigt man als Eingabewerte die entsprechende Ausgangsmatrix A0 und den Teiler q. Rückgabewert ist dann die veränderte Matrix A1.

2. Schritt: Eine Funktion blankinship() führt den kompletten erweiterten Euklidischen Algorithmus aus. Eingabewerte sind die Zahlen a und b. Rückgabewert ist ein Vektor mit drei Komponenten:

Im Wesentlichen wird eine Iteration durchgeführt, wobei in jedem Iterationsschritt die Funktion nextA() aufgerufen wird.

3. Schritt: Die Funktion blankinship() wird wieder so umgestaltet, dass zusätzlich Debug-Informationen abgefragt werden können. Diese sollen die Berechnungen so nachvollziehbar machen, wie sie in den Abbildungen 11 und 12 dargestellt sind.

1. Schritt: Implementierung der Zeilenumformungen

Die Funktion nextA() soll möglichst unabhängig vom Euklidischen Algorithmus implementiert werden. Sie hat die Aufgabe, eine gegebene Matrix A mit zwei Zeilenumformungen umzuwandeln und zurückzugeben:

Damit die letzte Operation ausgeführt werden kann, muss die Funktion nextA() einen weiteren Eingabewert besitzen; er wird hier mit divisor bezeichnet.

nextA <- function(A, divisor){
  stopifnot(is.matrix(A))
  stopifnot(nrow(A) == 2)
  stopifnot(is.wholenumber(x = divisor))
  
  A.TMP <- A[1, ]
  A[1, ] <- A[2, ]
  A[2, ] <- A.TMP - divisor * A[2, ]
  
  return(A)
}

Zeile 2 bis 4: Es werden einige Prüfungen ausgeführt; bei einer korrekten Anwendung des Euklidischen Algorithmus dürften die dort abgefangenen Fälle eigentlich nicht auftreten.

Zeile 6: Die Zeilenumformungen erfordern es, dass die erste Zeile der Matrix A zwischengespeichert wird.

Zeile 7 und 8: Die eigentlichen Zeilenumformungen wie oben beschrieben.

2. Schritt: Implementierung der Funktion blankinship()

Wie in den Erklärungen zu Abbildung 10 gezeigt wurde, muss lediglich aus den beiden Werten a und b die Matrix A aufgebaut werden. Mit ihr wird eine Iteration ausgeführt, deren Berechnungen jetzt in der Funktion nextA() erfolgen. Die Iteration kann dann abbrechen, wenn b gleich null ist. Die Bezeichnung "b == 0" erinnert an den Euklidischen Algorithmus; mit der Matrix A lautet diese Bedingung A[2, 1] == 0 .

Wenn die Iteration zu ihrem Ende kommt, muss aus der Matrix A der Rückgabewert extrahiert werden; nach Abbildung 10 ist es die erste Zeile der aktuellen Matrix A.

blankinship <- function(a, b){
  
  # Matrix A vorbereiten, (a, b) und E_2 aneinanderhängen
  A <- matrix(c(a, 1, 0, b, 0, 1), nrow = 2, byrow = TRUE)
  
  while(A[2, 1] > 0){
    q <- A[1, 1] %/% A[2, 1]
    A <- nextA(A = A, divisor = q)
  }
  return(A[1, ])
}

Zeile 1: Eingabewerte sind die beiden Zahlen a und b, von denen wieder angenommen wird, dass sie die üblichen Konventionen erfüllen ( a ≥ b > 0).

Zeile 4: Erzeugen der Matrix A0 (siehe Gleichung 1 in Abbildung 10).

Zeile 6 bis 9: Iteration bis b gleich null ist; b ist immer die untere Zahl der ersten Spalte von A.

Zeile 7: Berechnung des Teilers q aus den Werten der Matrix. Man beachte, dass der Rest r hier nicht berechnet werden muss. Dies geschieht nämlich in der Zeilenumformung in nextA(), siehe Zeile 8 der Implementierung von nextA().

Zeile 8: Die eigentlichen Berechnungen werden an die Funktion nextA() weitergereicht.

Zeile 10: Da der Rest erst innerhalb der Funktion nextA() berechnet wird, wird die letzte Matrix noch berechnet und daher ist Rückgabewert die erste Zeile der aktuellen Matrix A.

Insgesamt erkennt man, dass die Funktion blankinship() nur noch:

Aufrufe der Funktion blankinship() werden nach dem dritten Schritt gezeigt.

3. Schritt: Bereitstellen von Debug-Informationen

Schritt 1 und 2 haben gezeigt, dass mit gerade einmal 20 Zeilen Quelltext den erweiterten Euklidischen Algorithmus implementieren kann, wenn man nur an folgenden Größen interessiert ist:

Die Implementierung wird deutlich aufgebläht, wenn man die Zwischenergebnisse nachvollziehen möchte – vergleichbar zu den Berechnungen in Abbildung 11 und 12.

Dazu wird wieder ein zusätzlicher Eingabewert debug eingeführt, der steuert, ob weitere Informationen berechnet werden: blankinship(a, b, debug = FALSE) ; der default-Wert wird FALSE gesetzt.

Zusätzlich steuert der Eingabewert debug welche Ergebnisse im Rückgabewert abgelegt werden:

Ist debug = FALSE (der default-Wert), wird ein Vektor mit drei Komponenten zurückgegeben:

Bei debug = TRUE werden deutlich mehr Informationen während der Iteration aufgesammelt und als Debug-Information in einer Matrix abgespeichert:

Die Matrix ist dabei so aufgebaut, dass für jeden Iterationsschritt eine Zeile gebildet wird; in jeder Zeile stehen die genannten Größen.

Der Vektor, der im Fall von debug = FALSE gebildet wird und die Matrix mit den Debug-Informationen werden in eine Liste verpackt und zurückgegeben.

Mit der Unterscheidung der beiden Fälle debug = FALSE / TRUE ergibt sich aber ein Nachteil, den man eigentlich vermeiden sollte: Der Rückgabewert der Funktion blankinship(a, b, debug) ist entweder ein Vektor (default) oder eine Liste. Da aber die Debug-Informationen vermutlich bei ersten Tests oder zum Weiterentwickeln abgefragt werden, kann dieser Nachteil in Kauf genommen werden. Solange man nur an den Endergebnissen interessiert ist, wird man auf die Debug-Informationen verzichten.

Das folgende Skript zeigt die Implementierung:

blankinship <- function(a, b, debug = FALSE){
  # Eingabewerte speichern: für debug
  a0 <- a; b0 <- b
  
  # Matrix A vorbereiten, (a, b) und E_2 aneinanderhängen
  A <- matrix(c(a, 1, 0, b, 0, 1), nrow = 2, byrow = TRUE)
  
  if(debug == TRUE){
    # Matrix m vorbereiten
    m <- matrix(data = 0, nrow = b, ncol = 9, byrow = TRUE)
    colnames(m) <- c("q", "r", "a", "b", "e1.x", "e1.y", "e2.x", "e2.y", "check")
    v <- c(NA, NA, as.vector(A), NA)
    m[1, ] <- v
    n <- 1
  }
  
  while(A[2, 1] > 0){
    q <- A[1, 1] %/% A[2, 1]
    A <- nextA(A = A, divisor = q, debug = debug)
    
    if(debug == TRUE){
      check <- A[1, 2] * a0 + A[1, 3] * b0
      v <- c(q, A[2, 1], as.vector(A), check)
      m[n + 1, ] <- v
      n <- n + 1
    }
  }
  result <- A[1, ]
  
  if(debug == TRUE){
    lst <- list(ExtEuklid = result, debugInfo = head(x = m, n = n))
    return(lst)
  }
  return(result)
}

Der Quelltext lässt sich vermutlich leicht verstehen, wenn man ihn im Einsatz gesehen hat. Neu ist jetzt eigentlich nur die Matrix m, die vor der Schleife vorbereitet (Zeile 10 bis 13) und in der Schleife um jeweils eine Zeile erweitert wird (Zeile 22 bis 24; dazu wird der Zählindex n eingeführt). Es sollen wieder die bekannten Beispiele gezeigt werden:

# a = 24, b = 18, ohne Debug-Informationen
blankinship(a = 24, b = 18)
# [1]  6  1 -1

# a = 34, b = 24, ohne Debug-Informationen
blankinship(a = 34, b = 24)
# [1]  2  5 -7

# a = 24, b = 18, mit Debug-Informationen
blankinship(a = 24, b = 18, debug = TRUE)
# $ExtEuklid
# [1]  6  1 -1
# 
# $debugInfo
#       q  r  a  b e1.x e1.y e2.x e2.y check
# [1,] NA NA 24 18    1    0    0    1    NA
# [2,]  1  6 18  6    0    1    1   -1    18
# [3,]  3  0  6  0    1   -3   -1    4     6

blankinship(a = 34, b = 24, debug = TRUE)
# $ExtEuklid
# [1]  2  5 -7
# 
# $debugInfo
#       q  r  a  b e1.x e1.y e2.x e2.y check
# [1,] NA NA 34 24    1    0    0    1    NA
# [2,]  1 10 24 10    0    1    1   -1    24
# [3,]  2  4 10  4    1   -2   -1    3    10
# [4,]  2  2  4  2   -2    5    3   -7     4
# [5,]  2  0  2  0    5  -12   -7   17     2

Aufgabe:

Bestimmen Sie mit der Funktion blankinship() den größten gemeinsamen Teiler von a = 34 343 434 und b = 23 456 789.

Ist es möglich, die Zahl 12 als Linearkombination von a und b darzustellen?

Wenn ja, wie lauten die Koeffizienten k und l?

Lösung:

Das Beispiel soll demonstrieren, dass mit Durchprobieren der Teiler von a und b oder die Berechnung ihrer Primfaktorzerlegung sehr lange Zeit beansprucht. Zur Information:

Es sollte klar sein, dass man hier – etwa wenn man nur einen Taschenrechner zur Verfügung hat – mit dem Euklidischen Algorithmus schneller zum Ziel kommt.

Die Ausgabe mit blankinship() lautet:

blankinship(a = 34343434, b = 23456789, debug = TRUE)
# $ExtEuklid
# [1]        1 -3880718  5681817
# 
# $debugInfo
#        q        r        a        b     e1.x     e1.y    e2.x      e2.y    check
# [1,]  NA       NA 34343434 23456789        1        0       0         1       NA
# [2,]   1 10886645 23456789 10886645        0        1       1        -1 23456789
# [3,]   2  1683499 10886645  1683499        1       -2      -1         3 10886645
# [4,]   6   785651  1683499   785651       -2       13       3       -19  1683499
# [5,]   2   112197   785651   112197       13      -28     -19        41   785651
# [6,]   7      272   112197      272      -28      209      41      -306   112197
# [7,] 412      133      272      133      209   -86136    -306    126113      272
# [8,]   2        6      133        6   -86136   172481  126113   -252532      133
# [9,]  22        1        6        1   172481 -3880718 -252532   5681817        6
# [10,]   6        0        1        0 -3880718 23456789 5681817 -34343434        1

Die Zahl 12 lässt sich dann als Linearkombination von a und b darstellen, wenn sie ein Vielfaches von gcd(a, b) ist. Hier ist gcd(a, b) = 1 und somit sind die gesuchten Koeffizienten das 12-fache der Koeffizienten, die der Blankinship-Algorithmus liefert:

12 = 12 · (-3 880 718) · a + 12 · 5 681 817 · b = -46 568 616 · a + 68 181 804 · b.

Mit Hilfe von Satz 1 Punkt 6 lassen sich eventuell einfachere Koeffizienten finden. Auch hier sollte klar sein, dass eine Suche nach Koeffizienten ohne den Blankinship-Algorithmus sehr viel aufwendiger ist.

Aufgaben:

  1. Identifizieren Sie in den Ausgaben im Skript zum Aufruf der Funktion blankinship() die Matrizen, die in Abbildung 11 und 12 dargestellt waren.
  2. Oben wurde gesagt, dass die Funktion blankinship() die Konvention a ≥ b > 0 erfüllen soll. Testen Sie blankinship(a = 24, b = 34, debug = TRUE) und versuchen Sie eine Erklärung für das Verhalten zu geben.

Der Algorithmus von Stein

Es gibt einen erstaunlichen Algorithmus von William Stein (1961), der mit völlig anderen Operationen als der Euklidische Algorithmus arbeitet, aber auch den größten gemeinsamen Teiler zweier Zahlen a und b berechnet.

Der Algorithmus wird zwar in den meisten Fällen mehr Operationen ausführen müssen, aber sie sind deutlich einfacher, so dass er bei maschinennaher Programmierung deutlich schneller sein sollte.

Im Folgenden wird der Algorithmus kurz vorgestellt und eine Implementierung gezeigt. Es wird nicht bewiesen, dass der Algorithmus das richtige Ergebnis liefert.

Formulierung des Algorithmen von Stein in Pseudocode

Im Folgenden wird der Algorithmus von Stein im Pseudocode dargestellt; man erkennt, dass sehr elementare Rechenschritte vorzunehmen sind, die sich leicht implementieren lassen.

Eingabe; a, b
c <- 1
Solange(a != b){
    # Fallunterscheidung
    # 1. Fall
    falls (a gerade und b gerade)
        a = a/2; b = b/2; c = 2*c;
    # 2. Fall
    falls (a gerade und b ungerade)
        a = a/2;
    # 3. Fall
    falls (a ungerade und b gerade)
        b = b/2
    # 4. Fall
    falls (a ungerade und b ungerade)
        a = abs(a - b); b = min(a, b); 
}
Rückgabewert: a * c

Salopp kann man den Algorithmus so formulieren:

Implementierung des Algorithmus von Stein

Das folgende Skript zeigt eine Implementierung des Algorithmus von Stein. Da oft geprüft werden muss, ob Zahlen gerade sind, wird die Funktion isEven() implementiert. Sie gibt TRUE zurück, wenn alle Komponenten des Eingabevektors gerade sind, andernfalls FALSE.

isEven <- function(v){ 
    ifelse (test = all(v %% 2 == 0), yes = TRUE, no = FALSE)
}

# Tests:
isEven(5)       # FALSE
isEven(c(3, 2))   # FALSE
isEven(c(0, 2))   # TRUE

Die Implementierung des Algorithmus von Stein wird wieder mit ausführlichen Debug-Informationen versehen:

stein <- function(a, b, debug = FALSE){
  v <- c(a, b)
  c <- 1
  if(debug){
    n <- 1; case <- 1;
  }
  
  while(v[1] != v[2]){
    
    # Fallunterscheidung für a, b
    if( isEven(v) ){    # a, b gerade
      v <- v / 2; c <- 2 * c; case <- 1
    } else {
      if( isEven(v[1]) && !isEven(v[2]) ){    # a gerade, b ungerade
        v[1] <- v[1] / 2; case <- 2;
      } else {
        if( !isEven(v[1]) && isEven(v[2]) ){    # a ungerade, b gerade
          v[2] <- v[2] / 2; case <- 3;
        } else {
          if( !isEven(v) ){         # beide ungerade
            tmp <- v
            v[1] <- abs(tmp[1] - tmp[2]); v[2] <- min(tmp); case <- 4
          }
        }
      }
    }
    if(debug){
      n <- n + 1
      cat("a, b, c: ", v, c, "\n")
      cat("case: ", case, "\n\n")
    }
  }
  if(debug){
    cat("Anzahl der Schritte: ", n - 1, "\n")
  }
  return( v[1] * c )
}

Die Ausführung des Algorithmus führt zu sehr langen Ausgaben, da meist viele Iterationen durchlaufen werden.

# gcd(a = 24, b = 18)

stein(a = 24, b = 18, debug = TRUE)
# a, b, c:  12 9 2 
# case:  1 
# 
# a, b, c:  6 9 2 
# case:  2 
# 
# a, b, c:  3 9 2 
# case:  2 
# 
# a, b, c:  6 3 2 
# case:  4 
# 
# a, b, c:  3 3 2 
# case:  2 
# 
# Anzahl der Schritte:  5 
# [1] 6

Aufgabe:

Versuchen Sie eine geometrische Interpretation des Algorithmus von Stein zu formulieren:

Hinweise:

  1. Interpretieren Sie die Rechenschritte als Operationen mit zwei gegebenen Maßstäben der Länge a und b.
  2. Vergleichen Sie den Algorithmus von Stein mit der Suche nach einer vollständigen Parkettierung für ein Rechteck mit einem möglichst großen Quadrat (ähnlich wie in den Abbildungen 3 und 4).

Euklidischer Algorithmus ohne Division

Bei der Diskussion des Euklidischen Algorithmus konnte der Eindruck entstehen, dass er auf der Ganzzahl-Division beruht und erst der Algorithmus von Stein eine Alternative bietet, die vollständig ohne Divisionen auskommt. Dass dies falsch ist, zeigt das folgende Skript, das den Euklidischen Algorithmus ebenfalls ohne Divisionen (sondern nur mit Differenzen) implementiert. Es folgt zuerst die Version ohne Debug-Ausgaben, an der leichter zu erkennen ist, wie der Algorithmus arbeitet und dann die Version mit Debug-Ausgaben, die zum Testen des Algorithmus besser geeignet ist:

# ohne Debug-Ausgaben
gcd.diff <- function(a, b){
  if(a == b){
    return(a)
  } else {
    if(a > b){
      return(gcd.diff(a - b, b))
    } else {
      return(gcd.diff(a, b - a))
    }
  }
}

# mit Debug-Ausgaben
gcd.diff <- function(a, b, debug = FALSE){
  if(a == b){
    if(debug){
      cat("Ende der Rekursion mit a, b: ", a, b, "\n")
    }
    return(a)
  } else {
    if(a > b){
      if(debug){
        cat("a, b: ", a, b, "\n")
      }
      return(gcd.diff(a - b, b, debug = debug))
    } else {
      if(debug){
        cat("a, b: ", a, b, "\n")
      }
      return(gcd.diff(a, b - a, debug = debug))
    }
  }
}

gcd.diff(a = 24, b = 18, debug = TRUE)
# a, b:  24 18 
# a, b:  6 18 
# a, b:  6 12 
# Ende der Rekursion mit a, b:  6 6 
# [1] 6

Aufgaben:

  1. Geben Sie an, welche rekursive Funktion der Algorithmus verwendet.
  2. Auf welchen Eigenschaften des größten gemeinsamen Teilers beruht dieser Algorithmus?
  3. Diskutieren Sie, welche Vor- und Nachteile der Algorithmus gegenüber dem Euklidischen Algorithmus (mit Ganzzahl-Division) hat!
  4. Geben Sie eine geometrische Interpretation des Algorithmus (ähnlich wie in Abbildung 3 und 4)!