Kettenbrüche

Aus den Iterationsgleichungen des Euklidischen Algorithmus gewinnt man nun die Kettenbruchentwicklung von a₀/a₁. Hierzu formen wir die Gleichungen um:

a₀/a₁	= n₀ + a₂/a₁, 0 < a₂ < a₁, n₀  ∈  ℕ⁺,
a₁/a₂	= n₁ + a₃/a₂, 0 < a₃ < a₂, n₁  ∈  ℕ⁺,
a₂/a₃	= n₂ + a₄/a₃, 0 < a₄ < a₃, n₂  ∈  ℕ⁺, usw.

Es folgt:

a₀/a₁ = n₀ + 1/(a₁/a₂) = n₀ + 1/(n₁ + a₃/a₂) = n₀ + 1/(n₁ + 1/(a₂/a₃)) = …,

was wir suggestiv notieren können als

Bricht das Verfahren ab, so erhalten wir also eine Darstellung von a₀/a₁ als Kettenbruch. Bricht das Verfahren nicht ab, so erhalten wir einen „unendlichen Kettenbruch“ − die genaue Definition geben wir unten. Insgesamt ergibt sich nach dem obigen Satz für die Wahl a₁ = 1 eine endliche Kettenbruchentwicklung einer rationalen Zahl a₀ ≥ 1, und eine unendliche Kettenbruchentwicklung einer irrationalen Zahl a₀ ≥ 1.

Kettenbrüche sind der moderne algebraische Ausdruck der antiken Wechselwegnahme. Vor allem Euler und Lagrange haben die Kettenbrüche im 18. Jahrhundert zur Reife gebracht. „At the end of the eightteenth century, a chorus of mathematicians sang forth the wonders of continued fractions“ [ Fowler 1999 ]. Diese Wunder wurden Gegenstand dicker Bücher, unter denen das von Oskar Perron herausragt. Wir wollen hier nur die einfachsten Dinge entwickeln.

Der sich ergebende glatte Übergang von einer irrationalen Zahl a₀ > 1 zu einer unendlichen Folge n₀, n₁, n₂, … von natürlichen Zahlen n_i ≥ 1 ist dabei von prinzipieller Bedeutung für das Folgende. Er stellt eine von den Brücken zwischen dem vertrauten Kontinuum und dem sog. Baireraum dar, der aus Folgen natürlicher Zahlen gebildet ist. Die arithmetischen Details der ebenso faszinierenden wie zuweilen nicht nur typographisch unangenehmen Kettenbrüche sind für diesen speziellen Aspekt zweitrangig.

Wir bleiben der Bedingung a₀ ≥ a₁ > 0 für Verhältnisse a₀/a₁ treu, und begnügen uns folglich mit Kettenbrüchen für reelle Zahlen größer oder gleich 1.

Definition (endliche Kettenbrüche)

Wir definieren für n₀, …, n_k  ∈  ℕ⁺ durch Rekursion über k ≥ 0:

[ n₀ ] = n₀,

[ n₀, …, n_k + 1 ] = n₀ + 1/[ n₁, …, n_k + 1 ].

Wir nennen die rationale Zahl [ n₀, …, n_k ] auch einen (endlichen) Kettenbruch der Tiefe k + 1.

Eine Verwechslung von [ n₀, n₁ ] als Kettenbruch mit dem abgeschlossenen reellen Intervall [ n₀, n₁ ] ist in der Regel aus Kontextgründen nicht zu befürchten.

In der Definition könnten wir statt n_i  ∈  ℕ⁺ auch allgemeiner reelle a_i ≥ 1 zulassen. Die Theorie konzentriert sich aber generell auf Kettenbrüche, die aus natürlichen Zahlen gebildet sind, und wir verwenden diese allgemeine Form nur inoffiziell.

Jeder Kettenbruch ist eine rationale Zahl ≥ 1. „Ganz unten“ in der Bruchdarstellung von [ n₀, …, n_k + 1 ] steht der Term n_k + 1/n_k + 1, und damit gilt

[ n₀, …, n_k, 1 ] = [ n₀, …, n_k + 1 ].

Der Bruch links hat die Tiefe k + 2, der Bruch rechts dagegen nur die Tiefe k + 1. Wir werden gleich zeigen, dass diese Beobachtung bereits die einzige Ausnahme zur Eindeutigkeit der Kettenbruchentwicklung darstellt.

Vielleicht ist es instruktiv, den Zusammenhang von Kettenbrüchen und dem Euklidischen Algorithmus an einem Beispiel vorzuführen. Wir wählen dabei für n₀, n₁, n₂, n₃, … die Folge 1, 2, 3, 4, …

Der Leser mit elementaren Programmierkenntnissen und Vergnügen an solchen Dingen ist aufgerufen, ein Programm für die beiden Algorithmen zu schreiben. Damit lassen sich viele arithmetische Feinheiten der Kettenbruchentwicklung spielerisch entdecken. Das folgende Beispiel wurde mit einem derartigen Programm gerechnet.

Beispiel zur Kettenbruchentwicklung

Übung

(i)	Berechnen Sie in Form eines gekürzten Bruches: [ 3 ], [ 3, 3 ], [ 3, 3, 4, 1 ], [ 3, 3, 5 ].

(ii)	Führen Sie den Algorithmus für das Zahlenpaar 53, 16 durch.

Wir wollen uns nun noch die Lage der Kettenbrüche auf der reellen Achse überlegen. Obige Beispielrechnung lässt hier einiges vermuten: Interessant ist etwa, dass [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] um einen immer besser approximierten Wert hin- und herzupendeln scheint. Dies ist in der Tat ganz allgemein richtig. Wir können dieses Pendelverhalten nachweisen, ohne uns allzutief in die Moräste der Bruchrechnung begeben zu müssen:

Für feste n₀, …, n_k ≥ 1 können wir den Kettenbruch [ n₀, …, n_k, n ] als eine Funktion in der Unbestimmten n  ∈  ℕ⁺ auffassen. Wir bezeichnen diese Funktion mit [ n₀, …, n_k, · ]. Es gilt also

[ n₀, …, n_k, · ] : ℕ⁺ → ℚ,

mit [ n₀, …, n_k, · ](n) = [ n₀, …, n_k, n ] für alle n  ∈  ℕ⁺. Die Funktion [ · ] (für den Sonderfall k = −1) ist offenbar die Identität auf ℕ⁺ und damit streng monoton wachsend. Allgemeiner gilt:

Satz (Monotonieverhalten von Kettenbrüchen)

Für alle n₀, …, n_k ≥ 1, k ≥ 0 gilt:

[ n₀, …, n_k , · ] ist streng monoton fallend, falls k gerade, und streng monoton wachsend, falls k ungerade.

Weiter gilt lim_n → ∞ [ n₀, …, n_k , n ] = [ n₀, …, n_k ].

Beweis

Die Aussage folgt durch Induktion nach k unter Verwendung der Rekursionsgleichung [ n₀, …, n_k, n ] = n₀ + 1/[ n₁, …, n_k, n ].

(Aus streng monoton fallend wird bei Kehrwertbildung streng monoton wachsend und umgekehrt.)

Am Ende des Kettenbruchs [ n₀, …, n_k, n ] steht der Term n_k + 1/n .

Hieraus folgt die Limeseigenschaft.

Damit gilt mit [ n₀, …, n_k, 1 ] = [ n₀, …, n_k + 1 ] insbesondere:

rng([ n₀, …, n_k , · ])	⊆ ] [ n₀, …, n_k ], [ n₀, …, n_k + 1 ] ]	für k gerade,
rng([ n₀, …, n_k , · ])	⊆ [ [ n₀, …, n_k + 1 ], [ n₀, …, n_k ] [	für k ungerade.

Fassen wir [ n₀, …, n_k , · ] in der offensichtlichen Weise als Funktion in einer reellen Größe x ≥ 1 auf, so gilt hier Gleichheit statt Inklusion.

Die Funktion [ n₀, …, n_k , · ] fällt oder wächst also von der angenommenen Intervallgrenze [ n₀, …, n_k + 1 ] streng monoton zur anderen Grenze [ n₀, …, n_k ], und das Wachstumsverhalten wechselt beim Übergang von k zu k + 1.

Interpretieren wir die Kettenbrüche derart, dass sie durch ihre Funktionswerte das Intervall [ 1, ∞ [ zerschneiden, so ergibt sich mit wachsender Tiefe der Kettenbrüche das folgende arithmetisch komplexe, aber strukturell recht überschaubare Bild:

Zunächst zerlegt die Funktion [ · ] das reelle Intervall [ 1, ∞ [ von links nach rechts in die Teilintervalle [ 1, 2 ], [ 2, 3 ], …, [ n, n + 1 ], …

Für festes n₀ zerlegt nun die Funktion [ n₀, · ] das Intervall [ n₀, n₀ + 1 ] von rechts nach links in die Intervalle [ n₀ + 1/2, n₀ + 1 ], [ n₀ + 1/3, n₀ + 1/2 ], …

Für fest gehaltene n₀ und n₁ zerlegt weiter die Funktion [ n₀, n₁, · ] das Intervall [ n₀ + 1/(n₁ + 1) , n₀ + 1/n₁ ] in unendlich viele Intervalle, diesmal wieder von links nach rechts. Und so weiter und so fort.

Sei r₀ = [ n₀, …, n_k ], wobei k gerade. Die Skizze zeigt die Zerlegung des Intervalls [ r₀, r₁ ] durch die Kettenbrüche r_i := [ n₀, …, n_k, i ] für i ≥ 1. Es gilt r₁ = [ n₀, …, n_k, 1 ] = [ n₀, …, n_k + 1 ], so dass die Zerlegung das Teilintervall [ [ n₀, …, n_k ], [ n₀, …, n_k + 1 ] ] der vorangehenden Zerlegung verfeinert. Für ungerade k erhalten wir ein gespiegeltes Bild mit r₀ > r₁ und wachsenden r_i für i ≥ 1.

Aus dieser einfachen Analyse des Werteverhaltens erhalten wir:

Korollar (Eindeutigkeitssatz für endliche Kettenbruchdarstellungen)

Mit Ausnahme des Schemas [ n₀, …, n_k, 1 ] = [ n₀, …, n_k + 1 ] ist die Darstellung einer rationalen Zahl als endlicher Kettenbruch eindeutig.

Korollar (Pendelverhalten von Kettenbrüchen)

Sei 〈 n_k | k  ∈  ℕ 〉 eine Folge in ℕ⁺, und sei q_k = [ n₀, …, n_k ] für k  ∈  ℕ. Dann gilt:

q₀ < q₂ < q₄ < … < … < q₅ < q₃ < q₁.

Das zweite Korollar lässt sich leicht auch direkt durch Induktion nach k beweisen. Zunächst ist q₁ = [ n₀, n₁ ] = n₀ + 1/n₁ > [ n₀ ] = q₀. Im Induktionsschritt von k nach k + 1 für k ≥ 1 nehmen wir zunächst an, dass k gerade ist und zeigen q_k + 1 > q_k. Nach I. V. ist aber [ n₁, …, n_k ] > [ n₁, …, n_k + 1 ] ≥ 1, also 1/[ n₁, …, n_k ] < 1/[ n₁, …, n_k + 1 ]. Damit haben wir: q_k = [ n₀, …, n_k ] = n₀ + 1/[ n₁, …, n_k ] < n₀ + 1/[ n₁, …, n_k + 1 ] = q_k + 1. Analog zeigt man für ungerade k ≥ 1, dass q_k + 1 < q_k. Nach I. V. gilt hier [ n₁, …, n_k ] < [ n₁, …, n_k + 1 ].

Für endliche Kettenbrüche r = [ n₀, …, n_i ] ist q₀ < q₂ < … < q_i = r < … < q₃ < q₁, wobei q_k = [ n₀, …, n_k ] für k ≤ i. Weiter gilt [ n₀, …, n_k, 1 ] ≤ r ≤ [ n₀, …, n_k ] für ungerade k ≤ i, und eine analoge Aussage gilt für gerade k ≤ i.

Nach dem Korollar existiert q_g = sup({ q_2n | n  ∈  ℕ }), und ebenso existiert q_u = inf ({ q_2n + 1 | n  ∈  ℕ }). Es gilt q_g ≤ q_u. Wir werden gleich zeigen, dass q_g = q_u gilt, und dass der gemeinsame Wert eine irrationale Zahl ist.

Aus dem Hauptsatz über den Euklidischen Algorithmus ergab sich, dass jede rationale Zahl größer oder gleich 1 als Kettenbruch dargestellt werden kann, d. h. es gilt

{ [ n₀, …, n_k ] | n₀, …, n_k  ∈  ℕ⁺, k ≥ 0 } = { q  ∈  ℚ | q ≥ 1 }.

Damit lassen die durch die Wertebereiche der Funktionen [ n₀, …, n_k, · ] gegebenen Intervallzerlegungen von [ 1, ∞ [ kein noch so kleines Teilintervall [ x, x + ε ] unzerschnitten (x ≥ 1, ε > 0). Der Leser, der sich mit diesen Zerlegungen angefreundet hat, sieht hiermit unmittelbar die Gültigkeit des folgenden Satzes:

Korollar (Hauptsatz über Kettenbrüche)

Sei 〈 n_k | k  ∈  ℕ 〉 eine Folge von natürlichen Zahlen n_k ≥ 1.

Dann existiert x = lim_k → ∞ [ n₀, …, n_k ], und x ist eine irrationale Zahl > 1.

Umgekehrt existiert für jede irrationale Zahl x > 1 eine eindeutige Folge 〈 n_k | k  ∈  ℕ 〉 von natürlichen Zahlen n_k ≥ 1 mit x = lim_k → ∞ [ n₀, …, n_k ].

Beweis

zur Existenz und Irrationalität des Limes:

Sei q_k = [ n₀, …, n_k ] für k  ∈  ℕ, und seien wieder q_g = sup({ q_2n | n  ∈  ℕ }) und q_u = inf ({ q_2n + 1 | n  ∈  ℕ }).

Annahme, es gibt ein r  ∈  ℚ mit q_g ≤ r ≤ q_u.

Sei [ m₀, …, m_i ] eine Kettenbruchdarstellung von r.

Dann existiert ein kleinstes k ≤ i mit m_k ≠ n_k, da sonst r = q_i.

Sei zunächst k ungerade, sodass [ n₀, …, n_k − 1, · ] streng monoton fällt.

Ist  m_k < n_k, so ist q_k = [ n₀, …, n_k ] ≤ [ m₀, …, m_k + 1 ] = [ m₀, …, m_k, 1 ] ≤ r.

Ist  m_k > n_k, so ist r ≤ [ m₀, …, m_k ] ≤ [ n₀, …, n_k + 1 ] = [ n₀, …, n_k, 1 ] ≤ q_k + 1.

In beiden Fällen ergibt sich ein Widerspruch zur Wahl von r.

Der Fall „k gerade“ wird analog widerlegt.

Also ist q_g = q_u  ∈  ℝ − ℚ (und q_g = q_u = lim_k → ∞ [ n₀, …, n_k ]).

zur Existenz und Eindeutigkeit einer Darstellung x = lim_k → ∞ [ n₀, …, n_k ]:

Sei x irrational. Wir definieren n_k rekursiv für k  ∈  ℕ durch:

n₀ = das eindeutige n ≥ 1 mit n < x < n + 1,

$n_{k + 1} = { \begin{matrix} „das n \geq 1 mit [n_{0}, …, n_{k}, n + 1] < x < [n_{0}, …, n_{k}, n] “ & falls k gerade, \\ „das n \geq 1 mit [n_{0}, …, n_{k}, n] < x < [n_{0}, …, n_{k}, n + 1] “ & falls k ungerade. \end{matrix}$

Nach oben existiert lim_k → ∞ q_k, wobei wieder q_k = [ n₀, …, n_k ] für k ≥ 0.

Nach Konstruktion ist aber q_2k < x < q_2k + 1 für alle k ≥ 0.

Also ist x = lim_k → ∞ q_k.

Induktion nach k zeigt, dass jede Darstellung von x die rekursive Definition der n_k erfüllt. Dies zeigt die Eindeutigkeit.

Lässt man als ersten Index n₀ beliebige ganze Zahlen zu, und verallgemeinert man die Definition eines Kettenbruchs in der offensichtlichen Weise, so erhält man ein analoges Resultat für alle irrationalen Zahlen x  ∈  ℝ.

Wir definieren schließlich:

Definition (unendliche Kettenbrüche)

Sei 〈 n_k | k  ∈  ℕ 〉 eine Folge von natürlichen Zahlen n_k ≥ 1.

Wir setzen [ n₀, n₁, … ] = [ 〈 n_k | n  ∈  ℕ 〉 ] = lim_k → ∞ [ n₀, …, n_k ], und nennen [ n₀, n₁, … ] auch einen unendlichen Kettenbruch.

Für k ≥ 1 heißt [ n₀, …, n_k − 1 ] der k-te Näherungsbruch an [ 〈 n_k | k  ∈  ℕ 〉 ].

Berechnung der Näherungsbrüche

Die Berechnung einer Reihe [ n₀ ], [ n₀, n₁ ], …, [ n₀, n₁, …, n_k ] von Näherungsbrüchen ist rechentechnisch aufwendig, da die rekursive Definition von [ n₀, …, n_k + 1 ] auf [ n₁, …, n_k ] zurückgreift und nicht auf [ n₀, …, n_k ]. Praktischer, und daneben auch von hohem theoretischen Interesse ist ein Verfahren, das zwei Hilfsreihen verwendet.

Definition (Hilfsreihen zur Berechnung der Näherungsbrüche)

Sei 〈 n_k | k  ∈  ℕ 〉 eine Folge von natürlichen Zahlen größer oder gleich 1.

Wir definieren rekursiv 〈 p_k | k ≥ − 2 〉 und 〈 q_k | k ≥ − 2 〉 durch:

p_{− 2}	= 0, p₋₁ = 1,
p_k	= n_k p_k − 1 + p_k − 2 für k ≥ 0,
q_{− 2}	= 1, q₋₁ = 0,
q_k	= n_k q_k − 1 + q_k − 2 für k ≥ 0.

Die p-Reihe beginnt also mit 0, 1, n₀, n₁ n₀ + 1, n₂ n₁ n₀ + n₂ + n₀, die q-Reihe mit 1, 0, 1, n₁, n₂ n₁ + 1. Ein Element der Reihe ist eine gewichtete Summe seiner beiden Vorgänger. Ist 〈 n_k | k  ∈  ℕ 〉 konstant, so ist die p-Reihe ein Linksshift der q-Reihe; es gilt dann p_k = q_k + 1 für k ≥ − 2. Ist speziell n_k = 1 für alle k  ∈  ℕ, so heißt 〈 q_k | k  ∈  ℕ 〉 die Folge der Fibonacci-Zahlen. Sie beginnt mit 1, 1, 2, 3, 5, 8, 13, …

Von rechenschmerzlindernder Bedeutung in der Theorie der Kettenbrüche ist nun der folgende Satz:

Satz (Berechnung der Näherungsbrüche)

Sei 〈 n_k | k  ∈  ℕ 〉 eine Folge von natürlichen Zahlen größer oder gleich 1, und seien 〈 p_k | k ≥ − 2 〉 und 〈 q_k | k ≥ − 2 〉 wie oben definiert.

Dann gilt [ n₀, …, n_k ] = p_k/q_k für alle k ≥ 0.

Beweis

Einfache Induktion nach k.

Weiter gilt für k  ∈  ℕ: p_k/q_k ist gekürzt, und die bestmögliche Approximation an den unendlichen Kettenbruch [ n₀, n₁, … ] unter allen Brüchen mit einem Nenner ≤ q_k. Wir verweisen den Leser hierzu auf die Literatur.

Die p- und q-Folgen ermöglichen also eine komfortable Berechnung der Näherungsbrüche von [ n₀, n₁, … ]. Ist umgekehrt x gegeben, so liefert der Euklidische Algorithmus angewendet auf x und 1 die Ziffern (die sog. Teilquotienten) n_k der Kettenbruchentwicklung [ n₀, n₁, … ] von x. Er lässt sich offenbar in der folgenden einfachen Form durchführen:

n_k	= „der ganzzahlige Anteil von 1/r_k − 1“,
r_k	= „der Nachkommaanteil von 1/r_k − 1“,

mit k ≥ 0 und r_{− 1} = 1/x.

Beispiel: Für die Näherung x = 3,14159265358979 an die Kreiszahl π liefert der Euklidische Algorithmus, angewendet auf x und 1, eine Folge beginnend mit den Zahlen 3, 7, 15, 1, 292. Die p-Folge beginnt dann mit 0, 1, 3, 22, 333, 355, 103993, die q-Folge mit 1, 0, 1, 7, 106, 113, 33102. Die ersten beiden rationalen Approximation an π sind also 3 und der seit Ur-Zeiten bekannte Bruch

22/7 ∼ 3,14285714.

Es folgen 333/106 ∼ 3,14150943 und 355/113 ∼ 3,14159292, sowie der noch genauere Bruch 103993/33102 ∼ 3,14159265.

Berechnung periodischer Kettenbrüche

Ist die Rekursionsgleichung [ n₀, …, n_k + 1 ] = n₀ + 1/[ n₁, …, n_k + 1 ] auch ungeeignet zur Berechnung der Folge der Näherungsbrüche, so lassen sich mit ihrer Hilfe dagegen die Werte gewisser unendlicher Kettenbrüche leicht identifizieren. Ein Grenzübergang liefert die Gleichung

[ n₀, n₁, … ] = n₀ + 1/[ n₁, n₂, … ]

für alle Kettenbrüche [ n₀, n₁, … ]. Periodische Kettenbrüche führen so zu quadratischen Gleichungen. Sei etwa x = [ 2, 2, 2, … ]. Dann gilt x = 2 + 1/x, also

x² − 2x − 1 = 0.

Wegen x ≥ 1 folgt hieraus x = 1 + $\sqrt{2}$ .

Weiter gilt z. B. [ 1, 2, 2, 2, … ] = $\sqrt{2}$ und [ 1, 1, 2, 1, 2, 1, 2, … ] = $\sqrt{3}$ . Nach dem Hauptsatz über Kettenbrüche und dem Satz von Pythagoras sind also insbesondere die Diagonale und die Seite eines Quadrats inkommensurabel, was wir gleich noch einmal anders beweisen werden. Es lässt sich zeigen, dass die irrationalen Lösungen quadratischer Gleichungen mit ganzzahligen Koeffizienten genau den periodischen unendlichen Kettenbrüchen entsprechen.

Der erste und edelste unter den unendlichen Kettenbrüchen ist vermutlich [ 1, 1, 1, … ]. Seine Näherungsbrüche sind durch die Quotienten q_k + 1/q_k der Reihe der Fibonacci-Zahlen gegeben. Dieser Bruch nun bringt uns endlich zurück zu Hippasos von Metapont und einer bis in die Neuzeit als magisch erachteten geometrischen Figur: Dem gleichseitigen Fünfeck, an dem selbst ein Teufel nicht gleichgültig vorüber gehen kann.