<< . .

. 17
( : 33)



. . >>

kommen.
7.5 Kettenbrüche * 129

7.5.1 Kettenbruchdarstellungen

Für a0 , . . . , an ∈ R mit a1 , . . . , an > 0 setzen wir
1
[a0 ; a1 , . . . , an ] := a0 + ∈ R.
1
a1 +
1
a2 +
..
. + a1
n

Für a0 , . . . , an ∈ Z mit a1 , . . . , an > 0 nennen wir das (n + 1)-Tupel

a0 ; a1 , . . . , an := ([a0 ], [a0 ; a1 ], . . . , [a0 ; a1 , . . . , an ])

einen endlichen Kettenbruch mit dem Wert

x := [a0 ; a1 , . . . , an ] ∈ Q .

Für jedes k = 0, . . . , n nennen wir [a0 ; a1 , . . . , ak ] ∈ Q den k-ten N¤herungsbruch
von a0 ; a1 , . . . , an .

Beispiel
Es gilt:
62 10 1 1 1 1
= 4+ = 4+ = 4+ = 4+ = 4+
3 1 1
13 13 13/10
1+ 1+ 1+
1
10 10/3
3+
3
1
= 4+ .
1
1+
1
3+
1
2+
1
Also gilt
62
= [4; 1, 3, 3] = [4; 1, 3, 2, 1] ,
13
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 ak ≥ 2
stets
[a0 ; a1 , . . . , ak ] = [a0 ; a1 , . . . , ak ’ 1, 1] .
Diese Nichteindeutigkeit können wir vermeiden, indem wir uns auf eigentliche Ket-
tenbrüche beschr¤nken: Wir nennen einen Kettenbruch a0 ; a1 , . . . , an eigent-
lich, wenn n = 0 oder an ≥ 2 gilt. Wir zeigen nun, dass sich jede rationale Zahl
eindeutig als eigentlicher Kettenbruch darstellen l¤sst.
130 7 Das RSA-Verfahren

7.5.2 Existenz und Eindeutigkeit von N¤herungsbrüchen

Wir benötigen eine Hilfsaussage.

Lemma 7.11
Es sei a0 ; a1 , . . . , an ein eigentlicher Kettenbruch mit dem Wert x ∈ Q. Dann gilt:

(i) n ≥ 1 ’ x = a0 + 1
.
[a1 ; a2 ,..., an ]

(ii) a0 = x .

Beweis. Die Aussage (i) ist klar. Im Fall n = 0 gilt a0 = x = x und somit (ii). Im
Fall n ≥ 1 ist x = a0 + [a ; a 1 a ] , und [a1 ; a2 , . . . , an ] > 1 wegen an ≥ 2, sodass
1 2 ,..., n
a0 ¤ x < a0 + 1, also a0 = x ; folglich gilt (ii) auch in diesem Fall.

Satz 7.12
Jede rationale Zahl besitzt genau eine Darstellung als eigentlicher Kettenbruch.

Beweis. Für x = b ∈ Q mit a ∈ Z und b ∈ N liefert der euklidische Algorithmus
a

ganze Zahlen a0 , a1 , . . . , an und r1 , . . . , rn mit:
« §a r1
0 ¤ rb1 < 1
0 ¤ r1 < b ⎪ ⎪ b = a0 + b ,
a = a0 b + r1 , ⎪b
⎪⎪
0 < r 2 < r 1 ⎪ ⎪ r1 = a 1 + r1 ,
r2
0 < r2 < 1
⎪⎪
b = a1 r1 + r2 , ⎪⎪
⎪ ⎪ r1 r1
⎪⎪
¬ ⎨ r = a 2 + r3 , 0 < r3 < 1
r1 = a2 r2 + r3 , 0 < r3 < r2 r2 r2

2
. . . . . .
⎪⎪
. . . . . .
⎪⎪
. . . . . .
⎪ ⎪r
⎪ ⎪ n’2
⎪⎪
rn’2 = an’1 rn’1 + rn , 0 < rn < rn’1⎪ ⎪ r ⎪ ⎪ n’1 = an’1 + rn’1 , 0 < rn’1 < 1
rn rn
⎭ ⎪r © n’1
rn’1 = an rn
rn = a n

Falls b | a, ist x = a0 . Es ist dann a0 mit a0 ∈ Z ein eigentlicher Kettenbruch mit
dem Wert x. Falls b a, folgt offenbar a1 , . . . , an ∈ N; und es ist a0 ; a1 , . . . , an ein
Kettenbruch mit Wert x. Wegen rn’1 > rn ist an ≥ 2. Folglich ist der Kettenbruch
eigentlich. Wir begründen die Eindeutigkeit: Es gelte

x = [a0 ; a1 , . . . , an ] = [b0 ; b1 , . . . , bm ]

mit a0 , b0 ∈ Z, ai , b j ∈ N für i, j ≥ 1 und an ≥ 2, bm ≥ 2, falls n, m ≥ 1. Ohne
Einschr¤nkung sei n ¤ m. Wir schließen mit vollst¤ndiger Induktion nach n. Im
Fall n = 0 gilt x = a0 = a0 ∈ Z. Lemma 7.11 liefert b0 = x = a0 = 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 a0 = x = b0 und daher

[a1 ; a2 , . . . , an ] = [b1 ; b2 , . . . , bm ] .

Mit der Induktionsvoraussetzung folgt n = m und ai = bi für i = 1, . . . , n.
7.5 Kettenbrüche * 131

Bemerkung
Der zu b ∈ Q (existierende und eindeutig bestimmte) eigentliche Kettenbruch
a

a0 ; a1 , . . . , an kann also mithilfe des euklidischen Algorithmus ef¬zient berech-
net werden. Das wird für den Wiener-Angriff auf das RSA-Kryptosystem wichtig
sein.


7.5.3 Ermittlung der N¤herungsbrüche

Wir geben nun ein Verfahren an, mit dem wir die Z¤hler und Nenner der N¤he-
rungsbrüche [a0 ; a1 , . . . , ak ] aus der Kettenbruchdarstellung a0 ; a1 , . . . , an be-
stimmen können. Dazu benutzen wir die folgende Aussage:

Lemma 7.13
Es seien a0 ∈ Z und a1 , . . . , an ∈ N gegeben, und pk bzw. qk seien rekursiv erkl¤rt
durch
p1 := a1 a0 + 1 ; pk := ak pk’1 + pk’2 für k ≥ 2 ;
p0 := a0 ;
qk := ak qk’1 + qk’2 für k ≥ 2 .
q0 := 1 ; q1 := a1 ;

Dann gilt für alle möglichen k = 0, 1, . . .:
pk , qk ∈ Z, 1 = q0 ¤ q1 ; und qk < qk+1 , falls k ≥ 1; qk ≥ k.
(a)
pk+1 qk ’ qk+1 pk = (’1)k ,
(b)
pk+2 qk ’ qk+2 pk = (’1)k ak+2 ,
(c)
ak pk’1 +pk’2
Für jedes k ≥ 2 gilt [a0 ; a1 , . . . , ak ] =
(d) ak qk’1 +qk’2 .
pk
[a0 ; a1 , . . . , ak ] = und ggT(pk , qk ) = 1.
(e) qk ,

Beweis. (a) folgt direkt aus den De¬nitionen.
(b) stimmt für k = 0: p1 q0 ’ q1 p0 = (a1 a0 + 1) · 1 ’ a1 a0 = 1. Wenn die Aussage
für k ∈ N0 richtig ist, folgt

pk+2 qk+1 ’ qk+2 pk+1 = (ak+2 pk+1 + pk ) qk+1 ’ (ak+2 qk+1 + qk ) pk+1
= pk qk+1 ’ qk pk+1 = ’(’1)k = (’1)k+1 .
(c) Für jedes k ≥ 0 gilt

pk+2 qk ’ qk+2 pk = (ak+2 pk+1 + pk ) qk ’ (ak+2 qk+1 + qk ) pk
= ak+2 (pk+1 qk ’ qk+1 pk ) = (’1)k ak+2 .
(d) Für k = 2 gilt
a2 a0 a1 + a0 + a2 a p + p0
1
=21
[a0 ; a1 , a2 ] = a0 + = .
a2 a1 + 1 a2 q1 + q0
a1 + 1
a2
132 7 Das RSA-Verfahren

Die Behauptung sei richtig für ein k ≥ 2. Es folgt

(ak + ak+1 ) pk’1 + pk’2
1
1
[a0 ; a1 , . . . , ak+1 ] = [a0 ; a1 , . . . , ak + ]=
(ak + ak+1 ) qk’1 + qk’2
1
ak+1
ak+1 (ak pk’1 + pk’2 ) + pk’1 p + pk’1
a
= k+1 k
= .
ak+1 (ak qk’1 + qk’2 ) + qk’1 ak+1 qk + qk’1
Damit ist (d) bewiesen.
(e) Für k = 0 bzw. k = 1 besagt die erste Behauptung:
a a +1
1
a0 p p
= 0 bzw. [a0 ; a1 ] = a0 + =01 = 1.
[a0 ] = a0 =
1 q0 a1 a1 q1
+p
ap p
Im Fall k ≥ 2 erh¤lt man mit (d): [a0 ; a1 , . . . , ak ] = ak qk’1 +q k’2 = q k .
k k’1 k’2 k
Nach der Aussage in (b) existieren zu pk und qk ganze Zahlen r, s mit

r qk + s pk = 1 .

Nach Lemma 4.8 (d) folgt hieraus ggT(pk , qk ) = 1.
Die Berechnung der N¤herungsz¤hler pk und N¤herungsnenner qk führt man
zweckm¤ßigerweise in folgendem Schema durch:
···
ak a0 a1 a2 a3
a1 a0 + 1 a2 p1 + p0 a3 p2 + p1 ···
pk a0
a2 q1 + q0 a3 q2 + q1 ···
1
qk a1

Beispiel
Wir berechnen die N¤herungsbrüche von 2; 1, 2, 3, 1, 2, 1, 3, 4 :
2 1 2 3 1 2 1 3 4
ak
2 3 8 27 35 97 132 493 2104
pk
1 1 3 10 13 36 49 183 781
qk
Damit sind die N¤herungsbrüche der Reihe nach
2 3 8 27 35 97 132 493 2104
,,, , , , , , .
1 1 3 10 13 36 49 183 781
Der Wert des eigentlichen Kettenbruchs 2; 1, 2, 3, 1, 2, 1, 3, 4 ist
2104
= 2.69398... .
781
Für die N¤herungsbrüche gilt
2 2104 38 2104 27 35 2104 97 132 2104 493
< <,< < < < < <
, , .
1 781 13 781 10 13 781 36 49 781 183
Diese Absch¤tzungen werden immer besser. Das ist kein Zufall, wir gehen die-
sem Ph¤nomen im übern¤chsten Abschnitt nach.
7.5 Kettenbrüche * 133

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¤u¬g unendlich. Bei einer rationalen Zahl x = b fan-
a

den wir die Koef¬zienten a0 , . . . , an der Kettenbruchentwicklung durch sukzessi-
ve Division mit Rest (siehe den Beweis zu Satz 7.12). Bei einer irrationalen Zahl x
bestimmt man die Koef¬zienten wie folgt. Man setzt x0 := x und a0 := x0 ∈ Z
und rekursiv für i ≥ 0:
1
(—) ai+1 := xi+1 ∈ N .
xi+1 := und
xi ’ ai
Für die so erhaltene Folge (ai ) nennt man
a0 ; a1 , a2 , . . .
pk
:= [a0 ; a1 , . . . , ak ] für jedes k ∈ N
den unendlichen Kettenbruch von x und qk
den k-ten N¤herungsbruch von x.

Bemerkung
Berechnet man die Zahlen a0 , a1 , a2 , . . . auf die geschilderte Art für eine ratio-
nale Zahl x, so gibt es einen Index n mit xn ∈ N, es ist dann a0 ; a1 , a2 , . . . , an
ein (endlicher) Kettenbruch mit Wert x.
pk
Man kann zeigen, dass die Folge der N¤herungsbrüche gegen x konver-
qk
giert.

Wir benötigen in Kapitel 11 nur das folgende Ergebnis zu unendlichen Ketten-
brüchen.

Lemma 7.14
Ist a0 ; a1 , a2 , . . . der unendliche Kettenbruch zur irrationalen Zahl x, so gilt für jedes
k ∈ N0 :
x = [a0 ; a1 , . . . , ak , xk+1 ] ,
wobei die Zahlen xk+1 durch die Rekursion (—) gegeben sind.

Beweis. Für k = 0 gilt:
1
[a0 ; x1 ] = a0 + = a0 + (x0 ’ a0 ) = x0 = x .
x1
Ist die Behauptung für k ’ 1 ∈ N korrekt, so folgt
1
x = [a0 ; a1 , . . . , ak’1 , xk ] = [a0 ; a1 , . . . , ak’1 , ak + ] = [a0 ; a1 , . . . , ak , xk+1 ] .
xk+1
Damit ist die Behauptung bewiesen.
134 7 Das RSA-Verfahren

7.5.5 Absch¤tzungen

Aus Lemma 7.13 gewinnen wir wichtige Absch¤tzungen:

Korollar 7.15
Es sei a0 ; a1 , . . . , an ein Kettenbruch mit dem Wert x, und wir de¬nieren wie in Lemma
p
7.13 die Zahlen pk , qk und setzen zudem rk := q k für k = 0, . . . , n. Dann gilt:
k

(’1)k
rk+1 ’ rk = für alle 0 ¤ k < n.
(a) qk qk+1

|rk+1 ’ rk | < für alle 1 ¤ k < n.
1
(b) q2
k


r2(k’1) < r2k < r2l+1 < r2l’1 für alle k, l ≥ 1 mit 2 k, 2 l + 1 < n.
(c)

r2 k < x < r2 l+1 für alle k, l ≥ 0 mit 2 k, 2 l + 1 < n.
(d)

Beweis. (a) ergibt sich aus Lemma 7.13 (b) mit Division durch qk qk+1 .
(b) folgt aus (a), weil qk+1 > qk nach Lemma 7.13 (a) für jedes k ≥ 1.
(c) Aus Lemma 7.13 (c) folgt
a2k
r2k ’ r2(k’1) = (’1)2(k’1) > 0 , d. h. r2 (k’1) < r2k
q2(k’1) q2 k

und
a2l+1
r2l+1 ’ r2l’1 = (’1)2l’1 < 0 , d. h. r2l+1 < r2l’1 .
q2l’1 q2l+1
(a) (’1)2l
Im Fall k ¤ l folgt r2k ¤ r2l < r2l+1 , weil r2l+1 ’ r2l = > 0; und im Fall
q2l q2l+1
k > l analog r2k+1 ’ r2k > 0, und r2k+1 < r2l+1 .
(d) folgt aus (c).



7.5.6 Charakterisierung von N¤herungsbrüchen

Man kann N¤herungsbrüche für rationale Zahlen charakterisieren. Dazu benöti-
gen wir einen Hilfssatz.

Lemma 7.16
Es seien x ∈ Q \ Z und p ∈ Z, q ∈ N gegeben; weiter sei x = [a0 ; a1 , . . . , an ] mit
p
an ≥ 2 und n ≥ 2. Mit q k sei der k-te N¤herungsbruch von x bezeichnet (vgl. Lemma
k
p pk
7.13). Gilt q < qk+1 für ein k ∈ {0, . . . , n ’ 2} und = qk , so folgt
q

|qk x ’ pk | < |q x ’ p| .
7.5 Kettenbrüche * 135

pk pk+1
= ±1, sodass wegen der Cra-
Beweis. Nach Lemma 7.13 (b) gilt det
qk qk+1
mer™schen Regel Zahlen a, b ∈ Z existieren mit

(—) pk a + pk+1 b = p , qk a + qk+1 b = q .

Wegen q < qk+1 impliziert dies a = 0. Und es gilt b = 0, weil aus (—) andernfalls
p pk
q = qk folgte. Im Fall a b > 0, d. h. a, b > 0 oder a, b < 0, entstünde wegen
q < qk+1 ein Widerspruch zur zweiten Gleichung in (—). Somit gilt a b < 0.
Nach Korollar 7.15 (d) haben qk x ’ pk = 0 und qk+1 x ’ pk+1 = 0 verschiedene
Vorzeichen, sodass

a (qk x ’ pk ) = 0 und b (qk+1 x ’ pk+1 ) = 0

gleiches Vorzeichen haben. Mit (—) folgt

|q x ’ p| = |a (qk x ’ pk ) + b (qk+1 x ’ pk+1 )|
= |a| |qk x ’ pk | + |b| |qk+1 x ’ pk+1 | > |qk x ’ pk | .

Das ist die Behauptung.

Mit diesem Lemma können wir nun die folgende Charakterisierung von N¤he-
rungsbrüchen beweisen:

Satz 7.17
pk
Es sei x ∈ Q. Wir bezeichnen die (gekürzten) N¤herungsbrüche von x mit qk . Dann gilt:

(a) Von zwei aufeinanderfolgenden N¤herungsbrüchen für x erfüllt mindestens einer
die Absch¤tzung
1
p
x’ k < .

<< . .

. 17
( : 33)



. . >>