Cryptography Reference
In-Depth Information
7.5.4 Unendliche Kettenbrüche
Auch irrationale Zahlen sind durch Kettenbrüche darstellbar. Wir entwickeln die-
se Theorie nur so weit, wie wir sie benötigen.
Da jeder endliche Kettenbruch eine rationale Zahl darstellt, sind Kettenbrüche
irrationaler Zahlen zwangsläufig unendlich. Bei einer rationalen Zahl
x
a
=
b
fan-
den wir die Koeffizienten
a
0
,...,
a
n
der Kettenbruchentwicklung durch sukzessi-
ve Division mit Rest (siehe den Beweis zu Satz 7.12). Bei einer irrationalen Zahl
x
bestimmt man die Koeffizienten wie folgt. Man setzt
x
0
:
=
x
und
a
0
:
=
x
0
∈
Z
und rekursiv für
i
≥
0:
1
x
i
−
(
∗
)
x
i
+
1
:
=
und
a
i
+
1
:
=
x
i
+
1
∈
N
.
a
i
Für die so erhaltene Folge
(
a
i
)
nennt man
a
0
;
a
1
,
a
2
,...
den
unendlichen Kettenbruch
von
x
und
p
k
q
k
=[
a
0
;
a
1
,...,
a
k
]
∈
N
:
für jedes
k
den
k
-ten
Näherungsbruch
von
x
.
Bemerkung
Berechnet man die Zahlen
a
0
,
a
1
,
a
2
, . . . auf die geschilderte Art für eine ratio-
nale Zahl
x
, so gibt es einen Index
n
mit
x
n
∈
N
, es ist dann
a
0
;
a
1
,
a
2
,...,
a
n
ein (endlicher) Kettenbruch mit Wert
x
.
Man kann zeigen, dass die Folge der Näherungsbrüche
p
k
q
k
gegen
x
konver-
giert.
Wir benötigen in Kapitel 11 nur das folgende Ergebnis zu unendlichen Ketten-
brüchen.
Lemma 7.14
Ist
a
0
;
a
1
,
a
2
, ...
der unendliche Kettenbruch zur irrationalen Zahl x, so gilt für jedes
k
∈
N
0
:
=[
]
x
a
0
;
a
1
,...,
a
k
,
x
k
+
1
,
(
∗
)
wobei die Zahlen x
k
+
1
durch die Rekursion
gegeben sind.
Beweis.
Für
k
=
0 gilt:
1
x
1
=
[
a
0
;
x
1
]=
a
0
+
a
0
+(
x
0
−
a
0
)=
x
0
=
x
.
Ist die Behauptung für
k
−
1
∈
N
korrekt, so folgt
1
x
k
+
1
]=[
x
=[
a
0
;
a
1
,...,
a
k
−
1
,
x
k
]=[
a
0
;
a
1
,...,
a
k
−
1
,
a
k
+
a
0
;
a
1
,...,
a
k
,
x
k
+
1
]
.
Damit ist die Behauptung bewiesen.
