Euklidischer Algorithmus und Kettenbrüche
Diese Seite behandelt den simplen, aber zugleich genialen Euklidischen Algorithmus und wie dieser mit der Kettenbruchdarstellung rationaler und irrationaler Zahlen zusammenhängt.
Der Euklidische Algorithmus
Schon 300 vor Christus befasste sich Euklid in seinem berühmten Werk "Die Elemente" mit der Frage, wie man das größte gemeinsame Maß, also den größten gemeinsamen Teiler ([math] ggT [/math]) zweier Zahlen finden kann.
Er entwickelte dazu einen Algorithmus, der auf folgendem Lemma beruht:
Lemma: Es seien [math] a, b, q, r \in \mathbb{N} [/math] und [math] b \gt 0 [/math] mit
- [math] a = bq + r, \hspace{20pt} 0 \le r \lt b [/math]
Dann gilt:[math] \hspace{10pt} ggT(a, b) = ggT(b, r). [/math]
Es gilt [math] a = bq + r [/math], also ist jeder gemeinsame Teiler von [math] b [/math] und [math] r [/math] auch ein Teiler von
[math] a [/math]. Stellt man die Gleichung nach [math] r [/math] um, erhält man [math] r = a - bq [/math] und somit ist jeder gemeinsame Teiler von [math] a [/math] und [math] b [/math] auch ein Teiler von [math] r [/math]. Die Zahlenpaare [math] (a, b) [/math] und [math] (b, r) [/math] haben also die gleichen gemeinsamen Teiler und somit auch den gleichen [math] ggT [/math]. |
Funktionsweise
Gesucht ist nun der größte gemeinsame Teiler zweier ganzer Zahlen [math] a [/math] und [math] b [/math] mit [math] a \gt b [/math]. Der Algorithmus funktioniert wie folgt:
- Teile [math] a [/math] durch [math] b [/math] und erhalten den Rest [math] r [/math].
- Ist [math] r = 0 [/math], ist [math] a [/math] ohne Rest durch [math] b [/math] teilbar und es gilt [math] ggT(a, b) = b [/math].
- Ist [math] r \neq 0 [/math], führe Schritt 1 für [math] b [/math] und [math] r [/math] durch.
- Führe die Schritte solange durch, bis [math] \text{Rest} \hspace{2pt} 0 [/math] bleibt. Dann lässt sich die Zahl als Produkt zweier anderer natürlicher Zahlen schreiben und es gilt:
Der letzte Rest, der von [math] 0 [/math] verschieden ist, ist der größte gemeinsame Teiler von [math] a [/math] und [math] b [/math].
Gesucht ist der [math] ggT [/math] von [math] a = 22 [/math] und [math] b = 16 [/math] |
---|
1. [math] \frac{a}{b} = \frac{22}{16} = 1 \hspace{10pt} \text{Rest} \hspace{5pt} 6 = r [/math]
2. Rest ungleich [math] 0 \Rightarrow [/math] Schritt 1 3. [math] \frac{b}{r} = \frac{16}{6} = 2 \hspace{10pt} \text{Rest} \hspace{5pt} 4 = s [/math] 4. [math] \frac{r}{s} = \frac{6}{4} = 1 \hspace{13pt} \text{Rest} \hspace{5pt} 2 = t [/math] 5. [math] \frac{s}{t} = \frac{4}{2} = 2 \hspace{13pt} \text{Rest} \hspace{5pt} 0 [/math] [math] \Rightarrow [/math] Der größte gemeinsame Teiler von [math] 22 [/math] und [math] 16 [/math] ist [math] 2 [/math]. |
Was sind Kettenbrüche?[1]
Bevor nun ein Zusammenhang zwischen dem Euklidischen Algorithmus und besagten Kettenbrüchen hergestellt werden kann, sollten zuerst ein paar Grundlegende Konzepte mit Notation eingeführt werden.
Ein (unendlicher(1)/endlicher(2)) Kettenbruch ist generell ein Konstrukt der Form:
[math] \hspace{10pt} [/math] [math] a_0 + \dfrac{b_1}{a_1 + \dfrac{b_2}{a_2 + \dfrac{b_3}{ \hspace{10pt} \ddots }}} \hspace{12pt} (1) [/math] [math] \hspace{10pt} [/math] oder [math] \hspace{10pt} [/math] [math] a_0 + \dfrac{b_1}{a_1 + \dfrac{b_2}{ a_{n-2} + \dfrac{\ddots}{ \hspace{10pt} a_{n-1} + \dfrac{b_n}{a_n}}}} \hspace{12pt} (2) [/math] [math] \hspace{10pt} [/math] [math] \hspace{10pt} [/math] mit [math] \hspace{20pt} a_i, b_j \in \mathbb{Z} \hspace{12pt} i \in \mathbb{N}_0 \hspace{12pt} j \in \mathbb{N}. [/math]
In unseren Beispielen reicht es jedoch aus, lediglich reguläre Kettenbrüche zu betrachten. Diese haben die Form:
[math] \hspace{10pt} [/math] [math] a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \dfrac{1}{ \hspace{10pt} \ddots }}} \hspace{12pt} (a) [/math] [math] \hspace{10pt} [/math] oder [math] \hspace{10pt} [/math] [math] a_0 + \dfrac{1}{a_1 + \dfrac{1}{ a_{n-2} + \dfrac{\ddots}{ \hspace{10pt} a_{n-1} + \dfrac{1}{a_n}}}} \hspace{12pt} (b) [/math] [math] \hspace{10pt} [/math] [math] \hspace{10pt} [/math] mit [math] \hspace{20pt} a_0 \in \mathbb{Z} \hspace{12pt} a_i \in \mathbb{N} \hspace{12pt} i \in \mathbb{N}. [/math]
Wie man erkennen kann, ist ein regulärer Kettenbruch somit durch seine Koeffizienten [math] a_0 [/math] und [math] a_i [/math] eindeutig gegeben. Die gängige Notation für diese Art von Kettenbruch ist wie folgt:
- [math] (a): \hspace{12pt} \left\lt a_0; a_1, a_2, \dots \right\gt [/math]
- [math] (b): \hspace{13pt} \left\lt a_0; a_1, a_2, \dots, a_n \right\gt [/math]
Zusätzlich lässt sich im (un-)endlichen Fall auch der Abschnitt oder Partialbruch des Kettenbruchs definieren. Für [math] 0 \le k \le n [/math] (endlich) bzw. [math] k \ge 0 [/math] (unendlich) definiert man:
$$ s_k := \left< a_0; a_1, a_2, \dots, a_k \right> $$
mit dazugehörigem [math] \text{Rest} [/math] :
$$ r_k := \left< a_k; a_{k+1}, a_{k+2}, \dots, a_n \right> \hspace{20pt} \text{bzw.} \hspace{20pt} r_k := \left< a_k; a_{k+1}, a_{k+2}, \dots \right> $$
[math][/math]
Kettenbruchdarstellung rationaler Zahlen [1]
Satz: Eine reelle Zahl ist genau dann rational, wenn sie sich als (regulären) endlichen Kettenbruch darstellen lässt.
Oder äquivalent: Eine reelle Zahl ist genau dann irrational, wenn ihre Kettenbruchdarstellung unendlich ist.
Beweis |
[math] \Leftarrow [/math]: Ein endlicher Kettenbruch stellt eine rationale Zahl dar, denn diesen erhält man durch endliche Summen und Produkte im Körper [math] \mathbb{Q} [/math]. [math] \Rightarrow [/math]: Dass eine rationale Zahl sich als endlicher Kettenbruch schreiben lässt, ist intuitiv vermutlich einleuchtend. Um dieses Ziel zu erreichen, wende folgenden Algorithmus an:
|
Beispiel
Als Beispiel betrachte [math] p = - \dfrac{75}{27} [/math].
Das Vorgehen ist analog zum euklidischen Algorithmus.
[math] -75 = -3 \cdot 27 + 6 [/math]
(Rest 6)
[math] \Rightarrow p = -3 + \dfrac{6}{27} = -3 + \dfrac{1}{\dfrac{27}{6}} [/math]
[math] 27 = 4 \cdot 6 + 3 [/math]
(Rest 3)
[math] \Rightarrow p = -3 + \dfrac{1}{4 + \dfrac{3}{6}} = -4 + \dfrac{1}{4 + \dfrac{1}{\dfrac{6}{3}}} [/math]
[math] 6 = 2 \cdot 3 + 0 [/math]
(Rest 0, also entspricht der vorherige Rest 3 dem [math] ggT(-75, 27) [/math] )
[math] \Rightarrow p = -3 + \dfrac{1}{4 + \dfrac{1}{2 + \dfrac{0}{3}}} = -3 + \dfrac{1}{4 + \dfrac{1}{2}} [/math]
(reguläre, endliche Kettenbruchdarstellung)
Geometrische Visualisierung von regulären Kettenbrüchen
Der behandelte und bewiesene Algorithmus zum berechnen der Kettenbruchdarstellung einer rationalen Zahl lässt sich auch visuell darstellen. Dafür stellt man den zu einer gegebenen Zahl [math] p \in \mathbb{Q} [/math] mit [math] p = \frac{k}{l}, \hspace{3pt} k,l \in \mathbb{N} [/math] gehörenden Bruch als Rechteck, mit der Höhe [math] k [/math] und der Länge [math] l [/math] dar. Zu beachten ist allerdings, dass die Visualisierung nur für positive Werte von [math] k [/math] und [math] l [/math] gut funktioniert (negative Seitenlängen ergeben keinen Sinn).
Dann wird nach folgendem Schema vorgegangen:
|
Beispiel 1: Gegebener Bruch: [math] \dfrac{17}{10} [/math][2]
$$ \dfrac{17}{10} \hspace{10pt} = \hspace{10pt} 1 + \dfrac{7}{10} \hspace{10pt} = \hspace{10pt} 1 + \dfrac{1}{\dfrac{10}{7}} \hspace{10pt} = \hspace{10pt} 1 + \dfrac{1}{1 + \dfrac{3}{7}} \hspace{10pt} = \hspace{10pt} 1 + \dfrac{1}{1 + \dfrac{1}{\dfrac{7}{3}}} \hspace{10pt} = \hspace{10pt} \color{Blue} 1 + \dfrac{1}{\color{Red} 1 + \dfrac{1}{\color{Green} 2 + \dfrac{1}{\color{Orange} 3}}} $$
Beispiel 2: Gegebener Bruch: [math] \dfrac{21}{17} [/math][3]
$$ \dfrac{21}{17} \hspace{10pt} = \hspace{10pt} 1 + \dfrac{4}{17} \hspace{10pt} = \hspace{10pt} 1 + \dfrac{1}{\dfrac{17}{4}} \hspace{10pt} = \hspace{10pt} \color{Blue} 1 + \dfrac{1}{\color{Red} 4 + \dfrac{1}{\color{Green} 4}} $$
Kettenbruchdarstellungen irrationaler Zahlen
Wie im vorigen Abschnitt gezeigt, haben irrationale Zahlen unendliche Kettenbruchdarstellungen. Dabei gilt, dass der Wert eines unendlichen Kettenbruchs der Form [math] \left\lt a_0; a_1, a_2, \dots \right\gt [/math] festgelegt ist als[4] [math] \lim \limits_{n \to \infty} \left\lt a_0; a_1, \dots, a_n \right\gt [/math]. Diese Festlegung ist für jeden regulären Kettenbruch sinnvoll, da gilt:
Die Folge der Partialbrüche eines jeden regulären Kettenbruchs konvergiert.
Wir definieren für alle [math] n \in \mathbb{N}_0 \\
K_n := \left\lt a_0; a_1, a_2, \dots, a_n \right\gt [/math]
des weiteren seien für alle [math] n \in \mathbb{N}_0 \; P_n, Q_n [/math] folgendermaßen definiert: [math] \begin{align} P_0 &:= a_0 \\ P_1 &:= a_1 a_ 0 + 1 \\ P_n &:= a_n P_n-1 + P_n-2 \\ \\ Q_0 &:= 1 \\ Q_1 &:= a_1 \\ Q_n &:= a_n Q_n-1 + Q_n-2 \end{align} [/math] Nun lässt sich induktiv zeigen, dass für alle [math] n \in \mathbb{N}_0 [/math] gilt [math] K_n = \dfrac{P_n}{Q_n} [/math] Induktionsanfang: [math] K_0 = a_0 = \dfrac{P_0}{Q_0} [/math] Induktionsschritt [math] (n \rightarrow n+1) [/math]: [math] \begin{align} K_n+1 &= \left\lt a_0; a_1, a_2, \dots, a_n+1 \right\gt \\ &=\left\lt a_0; a_1, a_2, \dots, a_n + \dfrac{1}{a_n+1} \right\gt \\ &= \dfrac{(a_n+\dfrac{1}{a_n+1})P_k-1 + P_k-2}{(a_n+\dfrac{1}{a_n+1})Q_n-1 + Q_n-2} \\ &= \dfrac{a_n+1 (a_n P_n-1 + P_n-2 )+P_n-1 }{a_n+1 (a_n Q_n-1 + Q_n-2 )+Q_n-1 } \\ &= \dfrac{a_n+1 P_n +P_n-1 }{a_n+1 Q_n +Q_n-1 } \\ &= \dfrac{P_n+1}{Q_n+1} |} == Beweis für die Irrationalität von \lt math\gt \sqrt{10} [/math] == Wir wissen, dass eine Zahl genau dann rational ist, wenn ihre Kettenbruchdarstellung endlich ist. Daher können wir zeigen, ob eine Zahl rational ist, indem wir ihre Kettenbruchdarstellung berechnen. [math] \begin{align} \sqrt{10} &= 3 + (\sqrt{10} - 3) = 3 + \dfrac{(\sqrt{10} - 3)(\sqrt{10} + 3)}{3 + \sqrt{10}} = 3 + \dfrac{1}{3 + \sqrt{10}} \\ \\ &= 3 + \dfrac{1}{3+3+\dfrac{1} {3 + \sqrt{10}}} = 3 + \dfrac{1}{6+\dfrac{1} {3 + \sqrt{10}}} \\ \\ &= 3 + \dfrac{1}{6+\dfrac{1} {6 + \dfrac{1} {3 + \sqrt{10}}}} \\ \\ &= 3 + \dfrac{1}{6+\dfrac{1} {6 + \dfrac{1} {6 + \dfrac{1} {\hspace{10pt} \ddots}}}} \end{align} [/math]
Berechnung des Wertes eines periodischen Kettenbruchs[5]Sei [math] \xi [/math] eine reelle Zahl gegeben durch [math] \: \xi := 4 + \dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{\hspace{10pt} \ddots}}}}}}} [/math]
[math] \: \xi \approx 4 + \dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{3}}} = \dfrac{47}{10} [/math]
[math] \theta := 2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{\hspace{10pt} \ddots}}}}} [/math]
[math] \Rightarrow \xi = 4 + \dfrac{1}{1+\dfrac{1}{\theta}} = 4 + \dfrac{\theta}{1 + \theta} = 4 + \dfrac{3 + \sqrt{15}}{6 + \sqrt{15}} = 4 + \dfrac{1 + \sqrt{15}}{7} = \dfrac{29 + \sqrt{15}}{7} [/math] Wie in dieser Beispielrechnung zu sehen, ist der Wert eines jeden rein periodischen Kettenbruchs die irrationale Lösung eines quadratischen Polynoms mit rationalen Koeffizienten, eine so genannte quadratische Irrationalzahl. Tatsächlich lässt sich aber noch mehr zeigen. Satz von Euler-Lagrange: Jeder periodische Kettenbruch ist eine quadratische Irrationalzahl und umgekehrt. Kettenbruchdarstellung von [math] \pi [/math][6]Da wir den ungefähren Wert von [math] \pi [/math] kennen, können wir es als regulären Kettenbruch entwickeln. Sei dazu [math] \left\lt a_0; a_1, a_2, \dots \right\gt := \pi [/math] Es gilt [math] 3\lt \pi \lt 4 \Rightarrow a_0 = 3 \\ \pi=3+(\pi-3) \; \; \; \; \dfrac{1}{8} \lt \pi-3 \lt \dfrac{1}{7} \Rightarrow a_1 = 7 \\ \pi=3+\dfrac{1}{7+(\dfrac{1}{\pi-3}-7)} \; \; \; \; \dfrac{1}{16} \lt \dfrac{1}{\pi-3}-7 \lt \dfrac{1}{15} \Rightarrow a_2 = 15 \\ \dots \\ [/math] [math] \pi[/math][math] = 3+\dfrac{1}{7+\dfrac{1}{15+\dfrac{1}{1+\dfrac{1}{292+\dfrac{1}{1+{\dfrac{1}{\hspace{10pt} \ddots}}}}}}} [/math] Werten wir die Partialbrüche dieses Kettenbruchs aus, sehen wir, dass sie eine gute Annäherung an [math] \pi [/math] liefern.
Da [math] \pi [/math] irrational ist und bisher keine Muster in dessen regulärem Kettenbruch gefunden wurden, können wir nur endliche Partialbrüche von diesem berechnen. Wenn wir uns aber nicht auf reguläre Kettenbrüche beschränken, gibt es Kettenbrüche von [math] \pi [/math], die Muster enthalten.[7] So zeigte Johann Heinrich Lambert: [math] \dfrac{4}{\pi}=1+\dfrac{1^2}{3+\dfrac{2^2}{5+\dfrac{3^2}{7+\dfrac{4^2}{9+\dfrac{5^2}{11+\dfrac{6^2}{\hspace{10pt} \ddots}}}}}} [/math] Von Leonhard Euler stammt die Entwicklung: [math] \pi= 1+\dfrac{1^2}{6+\dfrac{3^2}{6+\dfrac{5^2}{6+\dfrac{7^2}{6+\dfrac{9^2}{6+\dfrac{11^2}{\hspace{10pt} \ddots}}}}}} [/math] Siehe auchEinzelnachweise
Autoren
|