Cryptography Reference
In-Depth Information
7.5.1 Kettenbruchdarstellungen
Für
a
0
,...,
a
n
∈
R
mit
a
1
,...,
a
n
>
0 setzen wir
1
[
a
0
;
a
1
,...,
a
n
]
:
=
a
0
+
∈
R
.
1
+
a
1
1
+
a
2
.
.
.
1
a
n
+
∈
Z
>
(
+
)
Für
a
0
,...,
a
n
mit
a
1
,...,
a
n
0 nennen wir das
n
1
-Tupel
a
0
;
a
1
,...,
a
n
:
=([
a
0
]
,
[
a
0
;
a
1
]
,...,
[
a
0
;
a
1
,...,
a
n
])
einen
endlichen Kettenbruch
mit dem
Wert
x
:
=[
a
0
;
a
1
,...,
a
n
]
∈
Q
.
=
[
]
∈
Q
Für jedes
k
0, . . . ,
n
nennen wir
a
0
;
a
1
,...,
a
k
den
k
-ten
Näherungsbruch
von
a
0
;
a
1
,...,
a
n
.
Beispiel
Es gilt:
62
13
=
10
13
=
1
13/10
=
1
1
1
+
+
+
10
=
+
10/3
=
+
4
4
4
4
4
3
1
1
1
+
1
+
1
+
1
3
+
3
1
=
4
+
.
1
1
+
1
+
3
1
1
2
+
Also gilt
62
13
=[
4; 1, 3, 3
]=[
4; 1, 3, 2, 1
]
,
und es sind
[
4
]=
4,
[
4; 1
]=
5,
[
4; 1, 3
]=
4.75,
[
4; 1, 3, 3
]=
4.769... die Näherungs-
brüche.
≥
Allgemein gilt für jeden
k
-ten Näherungsbruch eines Kettenbruchs im Fall
a
k
2
stets
[
]=[
−
]
.
Diese
Nichteindeutigkeit
können wir vermeiden, indemwir uns auf
eigentliche
Ket-
tenbrüche beschränken: Wir nennen einen Kettenbruch
a
0
;
a
1
,...,
a
k
a
0
;
a
1
,...,
a
k
1, 1
a
0
;
a
1
,...,
a
n
eigent-
lich
, wenn
n
2 gilt. Wir zeigen nun, dass sich jede rationale Zahl
eindeutig als eigentlicher Kettenbruch darstellen lässt.
=
0 oder
a
n
≥
