Appendix A: Mathematical Facts - Codes: The Guide to Secrecy from Ancient to Modern Times - page 495

A.7 Continued Fractions

For Appendix C, we will need some basic ideas from the theory of continued
fractions as follows.
Definition A.41 ( Continued Fractions )
If q j ∈ R

+ for j> 0 , then an

where j ∈ Z is nonnegative and q j ∈ R

expression of the form,

1

α = q 0 +

1
q 2 +

q 1 +

. . .

1

+

1
q k +1

q k +

. . .

is called a continued fraction . f q k ∈ Z for all k ≥ 0 , then it is called a

simple continued fraction , denoted by q 0 ; q 1 ,...,q k ,q k +1 ,... . If there exists a

nonnegative integer n such that q k =0 for all k

n , then the continued fraction
is called finite . If no such n exists, then it is called infinite .

≥

Definition A.42 ( Convergents ) Let n ∈ N and let α have continued fraction

+ when j> 0 . Then

expansion q 0 ; q 1 ,...,q n ,... for q j ∈ R

q 0 ; q 1 ,...,q k
is the k th convergent of α for any nonnegative integer k .

C k =

Theorem A.27 ( Finite Simple Continued Fractions are Rational )
Let α

∈ R . Then α ∈ Q if and only if α can be written as a finite simple

continued fraction.

Proof . See [167, Theorem 5.1.1, page 223].

✷

Theorem A.28 ( Representation of Convergents )
Let α =

q 0 ; q 1 ,... be a continued fraction expansion. Define two sequences

for k ∈ Z nonnegative:

A − 2 =0 ,A − 1 =1 ,A k = q k A k − 1 + A k − 2 ,

and

B − 2 =1 ,B − 1 =0 ,B k = q k B k − 1 + B k − 2 .

Then

C k = A k /B k = q k A k − 1 + A k − 2
q k B k − 1 + B k − 2

,

is the k th convergent of α for any nonnegative integer k .