O.Forster: Lineare Algebra

11. Der Euklidische Algorithmus

Der Euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier ganzer Zahlen ist einer der ältesten Algorithmen der Mathematik (über 2000 Jahre alt) und auch noch heute im Computer-Zeitalter aktuell. Bevor wir zur Beschreibung des Algorithmus kommen, soll zunächst der Begriff des größten gemeinsamen Teilers präzisiert werden.

Schreibweise. Für ganze Zahlen m, n schreibt man m | n, (und spricht: m teilt n), wenn m die Zahl n ohne Rest teilt, d.h. wenn es eine ganze Zahl q gibt mit n = qm. Definition. Seien a, b ∈ ℤ, nicht beide gleich 0. Eine Zahl d ∈ ℤ heißt größter gemeinsamer Teiler von a und b, wenn gilt:

a) d ist gemeinsamer Teiler von a und b, d.h. d | a und d | b.

b) Für jeden gemeinsamen Teiler d′ von a und b gilt: d′ | d. Für a = b = 0 wird der größte gemeinsame Teiler als 0 definiert.

Bemerkung. Der größte gemeinsame Teiler ist bis auf das Vorzeichen eindeutig bestimmt. (Wir unterstellen hierbei, dass es immer mindestens einen größten gemeinsamen Teiler gibt, was sich aber später mit dem Euklidischen Algorithmus von selbst ergeben wird.) Beweis. Seien d_{1} und d_{2} größte gemeinsame Teiler von a und b, (a und b nicht beide gleich 0). Aus der Definition folgt dann

d_{1} | d_{2} und d_{2} | d_{1}
⟹ d_{2} = q_{1}d_{1} und d_{1} = q_{2}d_{2} mit q_{1}, q_{2} ∈ ℤ
⟹ d_{2} = q_{1}q_{2}d_{2}
⟹ q_{1}q_{2} = 1 ⟹ q_{1} = ±1,

also d_{2} = ±d_{1}, q.e.d. Im folgenden wählen wir immer den nicht-negativen größten gemeinsamen Teiler zweier ganzer Zahlen a, b und bezeichnen ihn mit

gcd(a, b).

(Die Bezeichnung ist abgeleitet von engl. greatest common divisor.) Offenbar gilt

gcd(a, 0) = |a|, gcd(0, b) = |b|, gcd(±a, ±b) = gcd(a, b).

11. Euklidischer Algorithmus

11.1 Die Schulmethode zur Bestimmung des größten gemeinsamen Teilers zweier ganzer Zahlen a, b benutzt die Primfaktorzerlegung. Wir können annehmen, dass a > 0 und b > 0. Seien

a = ∏_{p} p^{e(a,p)} und b = ∏_{p} p^{e(b,p)}

die Primfaktorzerlegungen der beiden Zahlen. Dabei wird das Produkt formal über alle Primzahlen p erstreckt, aber für alle Primzahlen, die nicht in a als Faktor auftreten, ist der Exponent e(a, p) gleich 0 (und entsprechend für b), so dass effektiv nur endlich viele Faktoren auftreten. Setze

γ(p) := min(e(a, p), e(b, p)).

Dann gilt

gcd(a, b) = ∏_{p} p^{γ(p)}.

Beispiel. Sei

a := 980 = 2^{2} · 5 · 7^{2},
b := 126 = 2 · 3^{2} · 7.

Damit folgt gcd(a, b) = gcd(980, 126) = 2 · 7 = 14. Die Schulmethode eignet sich zur Bestimmung des größten gemeinsamen Teilers kleiner Zahlen, ist aber für große (z.B. hundertstellige) Zahlen, wie sie heute in manchen Anwendungen (z.B. in der Kryptographie) auftreten, gänzlich ungeeignet, denn die Faktorzerlegung großer Zahlen ist ein schwieriges Problem. Hier kommt nun der Euklidische Algorithmus zu Hilfe. Er stützt sich auf das Teilen mit Rest: Seien a, b ∈ ℤ, b ≠ 0. Dann gibt es eindeutig bestimmte ganze Zahlen q, r ∈ ℤ mit

a = qb + r und 0 ≤ r < |b|.

Lemma. Seien a, b ∈ ℤ, b ≠ 0, und a = qb + r mit q, r ∈ ℤ. Dann gilt

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

Beweis. Es ist nur zu zeigen

d | a, d | b ⟺ d | b, d | r.

11.2 “⇒” Es ist r = a − qb. Falls d die Zahlen a und b teilt, so teilt d auch r. “⇐” Aus a = qb + r folgt: Falls d die Zahlen b und r teilt, so teilt d auch a.

Wir können jetzt den Euklidischen Algorithmus beschreiben. Euklidischer Algorithmus. Seien a, b ganze Zahlen > 0. Setze a_{0} := a, a_{1} := b und führe sukzessive Divisionen mit Rest aus, bis die Division aufgeht:

a_{0} = q_{1}a_{1} + a_{2},  0 < a_{2} < a_{1},
a_{1} = q_{2}a_{2} + a_{3},  0 < a_{3} < a_{2},
⋮
a_{n−2} = q_{n−1}a_{n−1} + a_{n}, 0 < a_{n} < a_{n−1},
a_{n−1} = q_{n}a_{n} + 0.

(Da a_{1} > a_{2} > … > 0, muss das Verfahren nach endlich vielen Schritten abbrechen.) Dann gilt

a_{n} = gcd(a_{0}, a_{1}).

Beweis. Nach dem Lemma ist

a_{n} = gcd(a_{n}, 0) = gcd(a_{n−1}, a_{n}) = … = gcd(a_{1}, a_{2}) = gcd(a_{0}, a_{1}).

Beispiel. Für das oben betrachtete Zahlenpaar 980, 126 ergibt der Euklidische Algorithmus

980 = 7 · 126 + 98,
126 = 1 · 98 + 28,
98 = 3 · 28 + 14,
28 = 2 · 14,

also gcd(980, 126) = 14.

Bemerkung. Wir werden später mithilfe der Fibonacci-Zahlen eine Abschätzung für die Anzahl der Schritte, die beim Euklidischen Algorithmus nötig sind, ableiten.

Matrizen-Schreibweise. Die Gleichungen des Euklidischen Algorithmus lassen sich in Matrizen-Schreibweise umformen:

( \begin{matrix}a_{i} \\ a_{i+1} \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & −q_{i} \end{matrix} ) ( \begin{matrix}a_{i−1} \\ a_{i} \end{matrix} ) , i = 1, …, n − 1,
( \begin{matrix}a_{n} \\ 0 \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & −q_{n} \end{matrix} ) ( \begin{matrix}a_{n−1} \\ a_{n} \end{matrix} ) .

11.3 Setzt man zur Abkürzung

Q_{i} := ( \begin{matrix}0 & 1 \\ 1 & −q_{i} \end{matrix} ) ,

so ergibt sich durch Einsetzen der Gleichungen ineinander

( \begin{matrix}a_{n} \\ 0 \end{matrix} ) = Q_{n}Q_{n−1} · . . . · Q_{2}Q_{1} ( \begin{matrix}a_{0} \\ a_{1} \end{matrix} ) .

Mit

Q := Q_{n}Q_{n−1} · . . . · Q_{2}Q_{1} =: ( \begin{matrix}u & v \\ s & t \end{matrix} )

erhält man

( \begin{matrix}a_{n} \\ 0 \end{matrix} ) = Q ( \begin{matrix}a_{0} \\ a_{1} \end{matrix} ) = ( \begin{matrix}u & v \\ s & t \end{matrix} ) ( \begin{matrix}a \\ b \end{matrix} ) ⟹ a_{n} = ua + vb.

Damit haben wir folgende Aussage bewiesen.

Satz. Der größte gemeinsame Teiler d zweier ganzer Zahlen a, b lässt sich als ganzzahlige Linearkombination von a und b darstellen, d.h. es gibt u, v ∈ ℤ mit

d = ua + vb.

Anwendung. Wir betrachten den Spezialfall, dass b = p eine Primzahl ist und 0 < a < p. Dann gilt natürlich gcd(a, p) = 1. Nach dem obigen Satz gibt es dann u, v ∈ ℤ mit

1 = ua + vp.

Betrachtet man diese Gleichung modulo p, heißt dies 1 ≡ ua mod p, also

\overline{1} = \overline{u} · \overline{a} in ℤ/pℤ = 𝔽_{p}.

Daher ist \overline{u} das Inverse von \overline{a} im Körper 𝔽_{p}. Dies lässt sich zu einem effizienten Algorithmus zur Bestimmung des Inversen im Körper 𝔽_{p} ausbauen. Die Implementierung sei dem Studenten als Programmier-Übung empfohlen.

11.4