Chr.Nelius , Mathematik für Informatiker I (WS 2000/01) 8.1.2001

Der Rechenaufwand für den euklidischen Algorithmus hängt ab von

• dem Aufwand für einen Divisionsschritt

• der Anzahl der Divisionsschritte

Mit dem zweiten Punkt wollen wir uns etwas genauer beschäftigen.

\underline{\underline{(9.13) DEF:}} Seien a, b ∈ IN. Dann bezeichne D_{EA}(a, b) die Anzahl der Divisionsschritte, die für die Berechnung von ggT(a, b) mit Hilfe des EA erforderlich sind.

\underline{\underline{Beispiele :}}  a = 34 , b = 20  a = 34 , b = 21
34 = 1 · 20 + 14  34 = 1 · 21 + 13
20 = 1 · 14 + 6  21 = 1 · 13 + 8
14 = 2 · 6 + 2  13 = 1 · 8 + 5
6 = 3 · 2  8 = 1 · 5 + 3
5 = 1 · 3 + 2
D_{EA}(34, 20) = 4  3 = 1 · 2 + 1
2 = 2 · 1
D_{EA}(34, 21) = 7

Sind die Quotienten klein, so werden die Reste nur langsam kleiner, und es sind mehr Divisionsschritte auszuführen. Im zweiten Beispiel sind a und b gerade Fibonacci–Zahlen. Es ist nämlich 34 = F_{9} und 21 = F_{8}, und für ggT(F_{9}, F_{8}) werden genau 7 Divisionen benötigt, d.h. D_{EA}(F_{9}, F_{8}) = 7 . Allgemein gilt

\underline{\underline{(9.14) LEMMA:}} Für n ≥ 1 gilt ggT(F_{n+2}, F_{n+1}) = 1 und D_{EA}(F_{n+2}, F_{n+1}) = n

\underline{Bew:} Bei Division von F_{k+2} durch F_{k+1} ist 1 der Quotient und F_{k} , was wegen 0 ≤ F_{k} < F_{k+1} für k ≥ 2 sofort aus der Rekursionsgleichung F_{k+2} = F_{k+1} + F_{k} folgt.

F_{n+2} = 1 · F_{n+1} + F_{n}  (0 < F_{n} < F_{n+1})
F_{n+1} = 1 · F_{n} + F_{n−1}  (0 < F_{n−1} < F_{n})
F_{n} = 1 · F_{n−1} + F_{n−2}  (0 < F_{n−2} < F_{n−1})
⋮
F_{4} = 1 · F_{3} + \underbrace{F_{2}}_{=1}  (0 < F_{2} < F_{3})
F_{3} = 2 · F_{2}

Damit gilt ggT(F_{n+2}, F_{n+1}) = 1 für n ≥ 1 und D_{EA}(F_{n+2}, F_{n+1}) = n . •

\underline{\underline{(9.15) HILFSSATZ:}} Für a, b ∈ IN mit a > b gilt:

D_{EA}(a, b) = n ⟹ a ≥ F_{n+2} und b ≥ F_{n+1}

\underline{Bew:} Wir führen Induktion nach n. \underline{n = 1} Es gilt dann r_{2} = 0 und a = q_{1}b . Wegen a > b folgt dann b ≥ 1 = F_{2} und a ≥ 2 = F_{3}. (IV) Die Behauptung sei richtig für ein beliebiges n ∈ IN und beliebige a, b ∈ IN. Gelte D_{EA}(a, b) = n + 1 . Der erste Schritt des euklidischen Algorithmus lautet r_{0} = q_{1}r_{1} + r_{2} mit 0 < r_{2} < r_{1}. Für die Berechnung von ggT(r_{1}, r_{2}) werden dann genau n Divsionsschritte benötigt, d.h. D_{EA}(r_{1}, r_{2}) = n. Nach (IV) folgt dann aber \underline{b = r_{1} ≥ F_{n+2}} und r_{2} ≥ F_{n+1} . Also

a = r_{0} = q_{1}r_{1} + r_{2} ≥ r_{1} + r_{2} ≥ F_{n+2} + F_{n+1} = F_{n+3}

. •

\underline{\underline{(9.16) SATZ:}} (Lamé , 1844) Für a, b ∈ IN mit a > b ≥ 2 gilt:

a) D_{EA}(a, b) < 5 · log_{10}(b) + 1

b) Bezeichnet d die Anzahl der Dezimalstellen von b , so ist D_{EA}(a, b) ≤ 5 · d .

\underline{Bew:} : Setze m := D_{EA}(a, b) .

a) Für \underline{m = 1} gilt m < 5 log_{10}(b) + 1 , da log_{10}(b) > 0. Sei nun \underline{m ≥ 2}. Dann gilt b ≥ F_{m+1} > α^{m−1} mit α = \frac{1}{2}(1 + \sqrt{5}). Da die Funktion log_{10} streng monoton wachsend ist, ergibt sich log_{10}(b) > log_{10}(α^{m−1}) = (m − 1) log_{10}(α) > (m − 1) · \frac{1}{5} , da log_{10}(α) ≈ 0.20898 > 0.2 Also m − 1 < 5 · log_{10}(b)

b) Nach Voraussetzung ist b < 10^{d} , woraus log_{10}(b) < log_{10}(10^{d}) = d folgt. Nach a) ist daher m − 1 < 5 · d ∈ IN , also m ≤ 5 · d. •

\underline{\underline{BEM:}} Die Schranke in (9.16b) kann auch angenommen werden: D_{EA}(F_{7}, F_{6}) = 5, F_{6} = 8 , D_{EA}(F_{12}, F_{11}) = 10, F_{11} = 89 , D_{EA}(F_{17}, F_{16}) = 15, F_{16} = 987.

Wir wollen jetzt noch kurz den Fall betrachten, daß der ggT zweier Zahlen a und b gleich 1 ist. Dann gibt es x, y ∈ ZZ mit 1 = xa + yb.

\underline{\underline{(9.17) DEF:}} Zwei ganze Zahlen a und b heißen teilerfremd , wenn ggT(a, b) = 1 gilt.

\underline{\underline{(9.18) DEF:}} Die Funktion φ : IN ⟶ IN sei für n ∈ IN definiert durch

φ(n) := |{k | k ∈ IN, 1 ≤ k ≤ n, ggT(k, n) = 1}|

φ heißt Eulersche φ–Funktion.

\underline{\underline{Beispiele:}} φ(n) zählt also, wieviel Zahlen aus der Menge \{1, 2, 3, …, n\} zu n teilerfremd sind.

n = 1 : φ(1) = 1

n = 6 : 1 2̸ 3̸ 4̸ 5 6̸ φ(6) = 2

n = 7 : 1 2 3 4 5 6 7̸ φ(7) = 6

n = 12 : 1 2̸ 3̸ 4̸ 5 6̸ 7 8̸ 9̸ 1̸0 11 1̸2 φ(12) = 4

Analog zum Begriff des ggT’s definieren wir nun das kleinste gemeinsame Vielfache von zwei Zahlen.

\underline{\underline{(9.19) DEF:}} Seien a, b ∈ ZZ. Eine Zahl k ∈ ZZ heißt kleinstes gemeinsames Vielfaches (kgV) von a und b, wenn folgendes gilt:

i) k ≥ 0
ii) a | k und b | k
iii) ∀ v ∈ ZZ : a | v und b | v ⟹ k | v

Bezeichnung: k = kgV(a, b) Beispiel: kgV(35, 49) = 245 , kgV(−6, 18) = 18

\underline{\underline{BEM:}} Existiert ein kgV zweier Zahlen, so ist es eindeutig bestimmt (vgl. (9.9a,b)). Auch hier wird die Eindeutigkeit durch Bedingung i) erzwungen. ii) bedeutet, daß k ein gemeinsames Vielfaches von a und b ist. iii) besagt, daß jedes gemeinsame Vielfache von a und b von k geteilt wird. Gibt es also ein gemeinsames Vielfaches v ≠ 0, so folgt aus k | v, daß k = |k| ≤ |v| gilt, d.h. von allen gemeinsamen Vielfachen hat k den kleinsten Betrag.

\underline{\underline{(9.20) SATZ:}} Zu je zwei ganzen Zahlen a und b existiert genau ein kgV, und es gilt

ggT(a, b) · kgV(a, b) = |a · b|

Beispiel: kgV(35, −49) = 245 , ggT(35, −49) = 7 , kgV(35, −49) · ggT(35, −49) = 245 · 7 = 1715 = |35 · (−49)|

\underline{\underline{(9.21) BEM:}} Für a ≠ 0 oder b ≠ 0 gilt ggT(a, b) ≠ 0 , und es folgt

kgV(a, b) = \frac{| a · b |}{ggT(a, b)}

Damit haben ein Berechnungsverfahren für das kgV, wenn man den ggT mit Hilfe des EA bestimmt.

\underline{\underline{Beispiel:}} a = 1001414587, b = 42779171, ggT(a, b) = 1237 ⟹ kgV(a, b) = \frac{a · b}{1237} = 34631920662221

Einen mit dem EA vergleichbaren Algorithmus für die Berechnung des kgV’s gibt es nicht. Auch eine Darstellung des kgV’s, die der Darstellung des ggT’s als Vielfachsumme der beiden Zahlen entspricht, gibt es nicht.

Eine andere Berechnungsmethode für ggT und kgV basiert auf der Primfaktorzerlegung.

Der euklidische Algorithmus beruhte auf der Möglichkeit der Division mit Rest. Eine andere Anwendung der Division mit Rest ist die Darstellung einer Dezimalzahl bzgl. einer anderen Basiszahl b ≥ 2, etwa als Binärzahl (b = 2) oder als Oktalzahl (b = 8).

Beispiel:

\begin{aligned}196 & = & 65 · 3 & + & 1 \\ 65 & = & 21 · 3 & + & 2 \\ 21 & = & 7 · 3 & + & 0 \\ 7 & = & 2 · 3 & + & 1 \\ 2 & = & 0 · 3 & + & 2 \end{aligned}

Hierbei werden 196 und die entstehenden Quotienten durch 3 mit Rest geteilt. Man bricht ab, sobald ein Quotient 0 geworden ist. Ergebnis:

196 = (21021)_{3}

Ausführlich geschrieben:

b = 2 · 3^{4} + 1 · 3^{3} + 0 · 3^{2} + 2 · 3^{1} + 1 · 3^{0}

\underline{\underline{(9.22) SATZ:}} Sei b ≥ 2 eine feste natürliche Zahl. Dann läßt sich jede Zahl a ∈ IN darstellen in der Form

a = a_{n}b^{n} + a_{n−1}b^{n−1} + … + a_{1}b + a_{0}

mit n ∈ IN_{0} und eindeutig bestimmten Zahlen a_{k} ∈ {0, 1, …, b − 1} für alle k ∈ {0, 1, …, n} und a_{n} ≠ 0. Man schreibt:

a = (a_{n}a_{n−1} … a_{1}a_{0})_{b}

und nennt dies die Darstellung von a bzgl. der Basiszahl b.