Euklidischer Algorithmus und Kettenbrüche

Aus FunFacts Wiki
Zur Navigation springen Zur Suche springen

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 (ggT) zweier Zahlen finden kann.

Er entwickelte dazu einen Algorithmus, der auf folgendem Lemma beruht:

Lemma: Es seien a, b ganze Zahlen und b > 0 mit

a = bq + r, 0 ≤ r < b

Dann gilt ggT(a, b) = ggT(b, r).

Beweis
a = bq + r, also ist jeder gemeinsame Teiler von b und r auch ein Teiler von a.

Stellt man die Gleichung nach r um, erhält man r = a - bq und somit ist jeder gemeinsame Teiler von a und b auch ein Teiler von r.

Die Zahlenpaare (a, b) und (b, r) haben also die gleichen gemeinsamen Teiler und somit auch den gleichen ggT.

Funktionsweise

Gesucht ist nun also der größte gemeinsame Teiler zweier ganzer Zahlen a und b. Der Algorithmus funktioniert wie folgt:

  1. Teile a durch b und erhalten den Rest r.
  2. Ist r = 0, ist a ohne Rest durch b teilbar und es gilt ggT(a, b) = b. Ist r ≠ 0, ersetze a durch b und wiederhole Schritt 1.
  3. Führe die Schritte solange durch, bis Rest 0 bleibt. Der letzte Rest, der von 0 verschieden ist, ist der größte gemeinsame Teiler von a und b.
Beispiel
Gesucht ist der ggT von 22 und 16
1. 22/16 = 1, Rest 6

2. Rest ungleich 0 => Schritt 1

3. 16/6 = 2, Rest 4

4. 6/4 = 1, Rest 2

5. 4/2 = 2, Rest 0

=> Der größte gemeinsame Teiler von 22 und 16 ist 2.

Kettenbrüche und ihre geometrische Anschauung

Bevor nun ein Zusammenhang zwischen dem Euklidischen Algorithmus und Kettenbrüchen hergestellt werden kann, sollten zuerst ein paar Grundlegende Konzepte mit Notation eingeführt werden.

Ein Kettenbruch ist generell ein Konstrukt der Form:

[math] a_0 + \dfrac{b_1}{a_1 + \dfrac{b_2}{a_2 + \dfrac{b_3}{ \hspace{10pt} \ddots }}} [/math]

[math] 1 + \dfrac{1}{1 + \dfrac{1}{1 + \dfrac{1}{1 + \dfrac{1}{ \hspace{10pt} \ddots }}}} [/math]


[math][/math]

Kettenbruchdarstellung rationaler Zahlen [1]

Satz: Eine reelle Zahl ist genau dann rational, wenn sie sich als endlichen Kettenbruch darstellen lässt.

Beweis  
[math] \Rightarrow [/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] \Leftarrow [/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:
Sei [math] p \in \mathbb{Q} [/math], also von der Form [math] \dfrac{k}{l} [/math] mit [math] k \in \mathbb{Z}, l \in \mathbb{N} [/math].
Schritt 1: Setze [math] p_0 = \lfloor p \rfloor \in \mathbb{Z} [/math], ziehe also den ganzzahligen Anteil heraus. Damit entspricht [math] p_0 [/math] der eindeutigen ganzen Zahl, für die gilt: [math] k = p_0 \cdot l + r_0 [/math] mit [math] 0 \leq r_0 \lt l [/math].
Schritt 2:

  • Fall [math] r_0 \gt 0 [/math]: Es gilt die Gleichung [math] p = p_0 + \dfrac{r_0}{l} = p_0 + \dfrac{1}{\dfrac{l}{r_0}} [/math]. Wegen [math] l \gt r_0 [/math] und [math] l, r_0 \in \mathbb{N} [/math] folgt [math] p_1 = \lfloor \dfrac{l}{r_0} \rfloor \in \mathbb{N} [/math]. Ziehe also wie in Schritt 1 wieder den ganzzahligen Anteil heraus und betrachte die Gleichung [math] l = p_1 \cdot r_0 + r_1 [/math] mit [math] 0 \leq r_1 \lt r_0 [/math]. Unterscheide nun wieder die beiden möglichen Fälle [math] r_1 = 0 [/math], dann gilt [math] p = p_0 + \dfrac{1}{p_1} [/math], bzw. [math] r_1 \gt 0 [/math], dann wiederhole das Vorgehen. Wegen [math] r_0 \gt r_1 \gt r_2 \gt ... \geq 0 [/math] und [math] r_0, r_1, r_2, ... \in \mathbb{N} [/math] gibt es ein [math] n \in \mathbb{N} [/math] mit [math] r_n = 0 [/math]. Dann ist die endliche Kettenbruchdarstellung [math] p = p_0 + \dfrac{1}{p_1 + \dfrac{1}{p_2 + \dfrac{1}{p_3 + \dfrac{1}{... + \dfrac{1}{p_n}}}}} [/math].
  • Fall [math] r_0 = 0 [/math]: Dann gilt bereits [math] p = p_0 [/math] und [math] p [/math] besitzt eine endliche Kettenbruchdarstellung.

Beispiel

Als Beispiel betrachte [math] p = - \dfrac{34}{9} [/math].
[math] -34 = -4 \cdot 9 + 2 [/math]
[math] \Rightarrow p = -4 + \dfrac{2}{9} = -4 + \dfrac{1}{\dfrac{9}{2}} [/math]
[math] 9 = 4 \cdot 2 + 1 [/math]
[math] \Rightarrow p = -4 + \dfrac{1}{4 + \dfrac{1}{2}} = -4 + \dfrac{1}{4 + \dfrac{1}{\dfrac{2}{1}}} [/math]
[math] 2 = 2 \cdot 1 + 0 [/math]
[math] \Rightarrow p = -4 + \dfrac{1}{4 + \dfrac{1}{2 + \dfrac{0}{1}}} = -4 + \dfrac{1}{4 + \dfrac{1}{2}} [/math] (Abbruchbedingung: Rest 0)

Kettenbruchdarstellung irrationaler Zahlen

Beispiele für Kettenbruchdarstellungen irrationaler Zahlen

Beweis für die Irrationalität von [math] \sqrt{10} [/math]

Wir wissen, dass eine Zahl genau dann irrational ist, wenn ihre Kettenbruchdarstellung unendlich ist. Daher können wir zeigen, ob eine Zahl irrational 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]


Diese Darstellung bricht nie ab; [math] \sqrt{10} [/math] ist demnach irrational.

Berechnung des Wertes eines periodischen Kettenbruchs

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]


Um einen ungefähren Wert von [math] \xi [/math] zu berechnen, reicht es, den Wert eines Partialbruchs des Kettenbruchs zu bestimmen:

[math] \: \xi \approx 4 + \dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{3}}} = \dfrac{47}{10} [/math]


Da dieser Kettenbruch aber periodisch ist, können wir auch den exakten Wert von [math] \xi [/math] berechnen[2]. Dazu definieren wir

[math] \theta := 2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{3+\dfrac{1}{2+\dfrac{1}{\hspace{10pt} \ddots}}}}} [/math]


Es gilt [math] \: \theta = 2 + \dfrac{1}{3 + \dfrac{1}{\theta}} = 2 + \dfrac{\theta}{3\theta + 1} \\ \\ \Rightarrow \theta^{2} - 2\theta - \dfrac{2}{3} = 0 \\ \\ \Rightarrow \theta = \dfrac{3 + \sqrt{15}}{3} [/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]

Kettenbruchdarstellung von [math] \pi [/math][3]

[math] \pi = 3+\dfrac{1}{7+\dfrac{1}{15+\dfrac{1}{1+\dfrac{1}{292+\dfrac{1}{1+{\dfrac{1}{\hspace{10pt} \ddots}}}}}}} [/math]

Da wir den Wert von [math] \pi [/math] kennen, können wir es als regulären Kettenbruch entwickeln. Werten wir dessen Partialbrüche aus, sehen wir, dass sie eine gute Annäherung an [math] \pi [/math] liefern.

[math] \begin{align} \pi &= 3.1415926535897932384626433832795028... \\ &= [3,7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,...] \end{align} [/math]
Partialbruch ermittelter Bruch Wert als Dezimalzahl
[3] [math] \dfrac{3}{1} [/math] 3.00000000000000...
[3,7] [math] \dfrac{22}{7} [/math] 3.14285714285714...
[3,7,15] [math] \dfrac{333}{106} [/math] 3.14150943396226...
[3,7,15,1] [math] \dfrac{355}{113} [/math] 3.14159292035398...
[3,7,15,1,292] [math] \dfrac{103993}{33102} [/math] 3.14159265301190...
[3,7,15,1,292,1] [math] \dfrac{104348}{33215} [/math] 3.14159265392142...
[3,7,15,1,292,1,1] [math] \dfrac{208341}{66317} [/math] 3.14159265346744...
[3,7,15,1,292,1,1,1] [math] \dfrac{312689}{99532} [/math] 3.14159265361894...
[3,7,15,1,292,1,1,1,2] [math] \dfrac{833719}{265381} [/math] 3.14159265358108...

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, können wir einen Kettenbruch von [math] \pi [/math] errechnen, der ein Muster enthält.

Siehe auch

Einzelnachweise

  1. ↑ Johannes Klee: Endliche Kettenbrüche (2019), Masterseminar WiSe 19/20 an der TU Dortmund
  2. ↑ Thomas Boecker: Periodische Kettenbrüche Seminar zur Algebra und Zahlentheorie, WiSe 19/20 an der TU Dortmund
  3. ↑ Continued Fraction Approximations to [math] \pi [/math] University of Illinois - Department of Mathematics
Abgerufen von „https://funfacts.mathi.uni-heidelberg.de/index.php?title=Euklidischer_Algorithmus_und_Kettenbrüche&oldid=1776“