Cryptography Reference
In-Depth Information
Beweis.
Nach Lemma 7.13 (b) gilt det
p
k
p
k
+
1
=
±
1, sodass wegen der Cra-
q
k
q
k
+
1
mer'schen Regel Zahlen
a
,
b
∈
Z
existieren mit
(
∗
)
p
k
a
+
p
k
+
1
b
=
p
,
q
k
a
+
q
k
+
1
b
=
q
.
Wegen
q
<
q
k
+
1
impliziert dies
a
=
0. Und es gilt
b
=
0, weil aus
(
∗
)
andernfalls
p
q
p
k
q
k
=
>
>
<
folgte. Im Fall
ab
0, d. h.
a
,
b
0 oder
a
,
b
0, entstünde wegen
q
<
q
k
+
1
ein Widerspruch zur zweiten Gleichung in
(
∗
)
. Somit gilt
ab
<
0.
−
=
−
=
Nach Korollar 7.15 (d) haben
q
k
x
p
k
0 und
q
k
+
1
x
p
k
+
1
0 verschiedene
Vorzeichen, sodass
a
(
q
k
x
−
p
k
)
=
0 und
b
(
q
k
+
1
x
−
p
k
+
1
)
=
0
gleiches Vorzeichen haben. Mit
(
∗
)
folgt
|
qx
−
p
|
=
|
a
(
q
k
x
−
p
k
)+
b
(
q
k
+
1
x
−
p
k
+
1
)
|
=
|
||
−
p
k
|
+
|
||
−
p
k
+
1
| > |
−
p
k
|
a
q
k
x
b
q
k
+
1
x
q
k
x
.
Das ist die Behauptung.
Mit diesem Lemma können wir nun die folgende Charakterisierung von Nähe-
rungsbrüchen beweisen:
Satz 7.17
Es sei x
p
k
∈
Q
. Wir bezeichnen die (gekürzten) Näherungsbrüche von x mit
q
k
. Dann gilt:
(a)
Von zwei aufeinanderfolgenden Näherungsbrüchen für x erfüllt mindestens einer
die Abschätzung
<
p
k
q
k
1
2
q
k
−
x
.
vollständig gekürzt und gilt
q
<
p
q
p
p
q
1
∈
Q
−
(b)
Ist
x
2
q
2
, so ist
ein Näherungs-
bruch von x.
Beweis.
(a) Aus
≥
≥
p
k
q
k
1
2
q
k
p
k
+
1
q
k
+
1
1
2
q
k
+
1
x
−
und
x
−
p
k
+
1
folgt mit Korollar 7.15 (a), da
p
k
q
k
−
−
x
und
x
q
k
+
1
nach Korollar 7.15 (d) gleiches
Vorzeichen haben,
p
k
x
x
=
x
+
≥
1
q
k
q
k
+
1
=
p
k
+
1
q
k
+
1
p
k
p
k
+
1
q
k
+
1
1
2
q
k
+
1
2
q
k
+
1
q
k
−
+
−
q
k
−
x
−
