Cryptography Reference
In-Depth Information
7.5.2 Existenz und Eindeutigkeit von Näherungsbrüchen
Wir benötigen eine Hilfsaussage.
Lemma 7.11
Es sei
∈
Q
a
0
;
a
1
,...,
a
n
ein eigentlicher Kettenbruch mit dem Wert x
. Dann gilt:
1
(
)
≥
⇒
=
+
i
n
1
x
a
0
.
[
a
1
;
a
2
,...,
a
n
]
(
ii
)
a
0
=
x
.
Beweis.
Die Aussage (i) ist klar. Im Fall
n
=
0 gilt
a
0
=
x
=
x
und somit (ii). Im
1
≥
=
+
[
]
>
≥
Fall
n
1 ist
x
a
0
, und
a
1
;
a
2
,...,
a
n
1 wegen
a
n
2, sodass
[
a
1
;
a
2
,...,
a
n
]
≤
<
+
=
a
0
x
a
0
1, also
a
0
x
; folglich gilt (ii) auch in diesem Fall.
Satz 7.12
Jede rationale Zahl besitzt genau eine Darstellung als eigentlicher Kettenbruch.
a
Beweis.
Für
x
∈
N
liefert der euklidische Algorithmus
ganze Zahlen
a
0
,
a
1
,...,
a
n
und
r
1
,...,
r
n
mit:
=
b
∈
Q
mit
a
∈
Z
und
b
⎧
⎨
⎫
⎬
r
1
b
r
1
b
a
b
=
+
≤
<
a
0
,
0
1
=
+
≤
<
a
a
0
b
r
1
,
0
r
1
b
b
r
2
r
1
r
2
r
1
r
1
=
a
1
+
,
0
<
<
1
b
=
a
1
r
1
+
r
2
,
0
<
r
2
<
r
1
r
1
r
3
r
2
r
3
r
2
r
2
=
+
<
<
=
+
<
<
a
2
,
0
1
r
1
a
2
r
2
r
3
,
0
r
3
r
2
⇔
.
.
.
.
.
.
⎭
⎩
r
n
−
2
r
n
r
n
−
1
r
n
r
n
−
1
r
n
−
2
=
a
n
−
1
r
n
−
1
+
r
n
,0
<
r
n
<
r
n
−
1
r
n
−
1
=
a
n
−
1
+
,0
<
<
1
=
r
n
−
1
r
n
r
n
−
1
a
n
r
n
=
a
n
Falls
b
|
a
, ist
x
=
a
0
. Es ist dann
a
0
mit
a
0
∈
Z
ein eigentlicher Kettenbruch mit
demWert
x
. Falls
b
a
, folgt offenbar
a
1
,...,
a
n
∈
N
; und es ist
a
0
;
a
1
,...,
a
n
ein
>
≥
Kettenbruch mit Wert
x
. Wegen
r
n
−
1
2. Folglich ist der Kettenbruch
eigentlich. Wir begründen die Eindeutigkeit: Es gelte
r
n
ist
a
n
=[
]=[
]
x
a
0
;
a
1
,...,
a
n
b
0
;
b
1
,...,
b
m
∈
Z
∈
N
≥
≥
≥
≥
mit
a
0
,
b
0
,
a
i
,
b
j
für
i
,
j
1 und
a
n
2,
b
m
2, falls
n
,
m
1. Ohne
Einschränkung sei
n
≤
m
. Wir schließen mit vollständiger Induktion nach
n
.Im
=
=
=
∈
Z
=
=
=
Fall
n
0 gilt
x
a
0
a
0
. Lemma 7.11 liefert
b
0
x
a
0
x
, und es
gilt
m
=
0.
Es sei
n
≥
1, und die Behauptung sei für
n
−
1 richtig. Es folgt erneut mit Lemma
=
=
7.11, dass
a
0
x
b
0
und daher
[
a
1
;
a
2
,...,
a
n
]=[
b
1
;
b
2
,...,
b
m
]
.
Mit der Induktionsvoraussetzung folgt
n
=
m
und
a
i
=
b
i
für
i
=
1,...,
n
.
