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

Proof . See [167, Theorem 5.1.2, page 224].

✷

Theorem A.29 ( Irrationals Are Infinite Simple Continued Fractions )
Let α . Then α is irrational if and only if α has a unique infinite simple

continued fraction expansion ,

∈ R

α = α 0 = q 0 ; q 1 ,... = lim

k

C k ,

→∞

where

q k − 1 = α k − 1 with α k =1 / ( α k − 1 − q k − 1 ) and C k = A k /B k for k ∈ N .

Proof . See [167, Theorem 5.2.1, page 228]. ✷

Theorem A.30 ( Convergents of √ D )
Suppose that D> 0 is not a perfect square, n

< √ D .If ( x,y )

∈ Z , and | |

n

is a positive solution of

x 2 Dy 2 = n,

−

namely, x,y ∈ N , then x/y is a convergent in the simple continued fraction

expansion of √ D .

Proof . See [167, Theorem 5.2.5, page 232].

✷

Definition A.43 ( Periodic Continued Fractions )
An infinite simple continued fraction α = q 0 ; q 1 ,q 2 ,... is called periodic

if there exists an integer k ≥ 0 and ∈ N such that q n = q n + for all integers

n ≥ k . We use the notation,

α = q 0 ; q 1 ,...,q k − 1 ,q k ,q k +1 ,...,q + k − 1 ,

as a convenient abbreviation. The smallest such natural number = ( α ) is
called the period length of α , and q 0 ,q 1 ,...,q k − 1 is called the preperiod of α .
If k is the least nonnegative integer such that q n = q n + for all n ≥ k , then

q k ,q k +1 ,...,q k + − 1 is called the fundamental period of α.

If k =0 is the least such value, then α is said to be purely periodic , namely,

α = q 0 ; q 1 ,...,q − 1 .