Kettenbrüche

 Eine natürliche Frage ist, ob sich zu einer gegebenen Folge q₀, …, q_n positiver Zahlen zwei Zahlen a, b konstruieren lassen, die q₀, …, q_n als Quotientenfolge erzeugen, wenn der Euklidische Algorithmus durchgeführt wird. Wir schreiben hierzu die Rekursion des Algorithmus in der dividierten Form

a0a1  =  q0 + a2a1,  a1a2  =  q1 + a3a2,  …,  anan + 1  =  qn.

Dann gilt

ab  =  a0a1  =  q0 + a2a1  =  q0 + 1a1/a2  =  q0 + 1q1 + a3/a2  =  …

Diese Überlegung motiviert die folgende Definition:

 Die Kettenbruchnotation mit eckigen Klammern hat mit dem gleich bezeichneten kgV der Zahlen q₀, …, q_n nichts zu tun.

 Wie angestrebt gilt (Beweis als Übung):

 Die Bedingung q_n ≠ 1 lässt sich so einsehen: Der letzte Quotient q_n im Euklidischen Algorithmus kann nicht gleich 1 sein, da sonst a_n = a_n + 1 gelten würde, im Widerspruch zu a_n + 1 < a_n. Die Identität [ q₀, …, q_n, 1 ] = [ q₀, …, q_n + 1 ] (Zweideutigkeit der Kettenbruchdarstellung) illustriert diesen Sonderfall.

Unendliche Kettenbrüche

 Der Euklidische Algorithmus lässt sich allgemein für beliebige reelle Größen x, y > 0 erklären. Wir stellen einige Ergebnisse dieser Verallgemeinerung vor und verweisen den Leser für eine ausführlichere Darstellung auf die Literatur.

 Sind x > y > 0 gegeben, so können wir wie bisher wiederholt die kleinere von der größeren Zahl abziehen; diese Reduktion lässt sich erneut in Form von Einzelschritten oder in Form einer wiederholten Division mit Rest notieren. Das Verfahren bricht genau dann nach endlich vielen Schritten ab, wenn der Quotient der beiden Größen rational ist, d. h. wenn x/y  ∈  ℚ. Andernfalls ergibt sich eine unendliche Quotientenfolge q₀, q₁, …, q_n, …, die zur Definition

[ q₀, q₁, …, q_n, … ]  =  lim_{n → ∞} [ q₀, …, q_n ](unendlicher Kettenbruch)

Anlass gibt. Gilt x/y = [ q₀, q₁, q₂, … ], so erzeugt der Euklidische Algorithmus für x, y die Quotientenfolge q₀, q₁, … Speziell gilt dies für x = [ q₀, q₁, … ] und y = 1.

 Jeder unendliche Kettenbruch ist eine irrationale Zahl und jede irrationale Zahl größer als 1 lässt sich eindeutig als unendlicher Kettenbruch darstellen. Das berühmteste Beispiel ist

[ 1, 1, 1, … ]  =  $\frac{1+\sqrt{5}}{2}$.(goldener Schnitt)

Zum Beweis setzen wir x_n = [ 1, …, 1 ] (n Einsen) für alle n ≥ 1 und

x  =  [ 1, 1, 1, … ].

Nach Definition eines Kettenbruchs gilt x_n + 1 = 1 + 1/x_n. Damit erhalten wir

x  =  lim_n x_n  =  lim_n x_n + 1  =  lim_n (1 + ¹_xn)  =  1  +  ¹_x.

Hieraus folgt x² = x + 1 und aus der Lösungsformel für quadratische Gleichungen und x > 0 ergibt sich, dass x der goldene Schnitt ist. Aus dem zweiten Beispiel oben erhalten wir, dass die Quotienten f_n/f_n − 1 der Fibonacci-Zahlen gegen den goldenen Schnitt konvergieren.