Mathekram

Mathematik rein und angewandt, erforscht und unterrichtet (ein Matheblog)

Archive for Mai 2008

Endliche Kettenbrüche und der euklidische Algorithmus

Posted by Modulix - Mai 16, 2008

Zu Kettenbrüchen gibt es eine ausgefeilte Theorie (siehe etwa den Wikipedia-Eintrag), aber die Erstellung eines endlichen Kettenbruches erfordert keine Kenntnisse über Matrizen-Multiplikation oder ähnliches.

Wie erstelle ich etwa aus \frac{3}{11} einen Kettenbruch?

Ich wende den euklidischen Algorithmus darauf an, um den (natürlich bekannten) größten gemeinsamem Teiler zu finden:

3 = 0\cdot11+3

11=3\cdot3+2

3=1\cdot2+1

2=2\cdot1+0

Der Kettenbruch lautet damit:

\frac{3}{11}=\frac{1}{3+\frac{1}{1+\frac{1}{2}}}

Die Zahlen im Kettenbruch sind also nichts anderes als die Koeffizienten im euklidischen Algorithmus.

Ein weiteres Beispiel, bei dem der Zähler mal größer als der Nenner ist: \frac{14}{5}:

14=2\cdot5+4

5=1\cdot4+1

4=4\cdot4+0

Es folgt: \frac{14}{5}=2+\frac{1}{1+\frac{1}{4}}

Noch ein weiteres Beispiel: \frac{5}{13}:

Das ist der Quotient von zwei aufeinanderfolgenden Fibonaccizahlen. Diese Kettenbruchentwicklung deutet bereits an, dass allgemein gilt: \frac{fib_{n}}{fib_{n+1}}\rightarrow\frac{-1+\sqrt{5}}{2}, dass also die Quotienten aufeinanderfolgender Kettenbrüche gegen den goldenen Schnitt konvergieren. Dabei deutet sich auch an, dass der goldene Schnitt besonders schlecht zu approximieren ist.

8=0\cdot13+8

13=1\cdot8+5

8=1\cdot5+3

5=1\cdot3+2

3=1\cdot2+1

Es folgt: \frac{8}{13}=\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{2}}}}}.

Auf der Seite von Arndt Brünner kann man Kettenbrüche online berechnen. Dort ist auch noch einmal der Mechanismus erklärt.

 

Posted in Schulmathematik, Zahlentheorie | Leave a Comment »