Number Theory: An Introduction to Mathematics

1 The Continued Fraction Algorithm 181

(

pn pn− 1

qn qn− 1

)(

11

−an 0

)

=

(

pn− 2 pn

qn− 2 qn

)

,

from which, by taking determinants again, we get

pnqn− 2 −pn− 2 qn=(− 1 )nan (n≥ 0 ). (4)

It follows from (1)–(2) thatpnandqnare integers, and from (3) that they are
coprime. Sincean≥1forn≥1, we have

1 =q 0 ≤q 1 <q 2 <···.

Thusqn≥nforn≥1. (In fact, sinceqn≥qn− 1 +qn− 2 forn≥1, it is readily shown
by induction thatqn>τn−^1 forn>1, whereτ=( 1 +

√

5 )/ 2 .)

Sinceqn>0forn≥0, we can rewrite (3), (4) in the forms

pn/qn−pn− 1 /qn− 1 =(− 1 )n+^1 /qn− 1 qn (n≥ 1 ), ( 3 )′

pn/qn−pn− 2 /qn− 2 =(− 1 )nan/qn− 2 qn (n≥ 2 ). ( 4 )′

It follows that the sequence{p 2 n/q 2 n}is increasing, the sequence{p 2 n+ 1 /q 2 n+ 1 }is
decreasing, and every member of the first sequence is less than every member of the
second sequence. Hence both sequences have limits and actually, sinceqn→∞,the
limits of the two sequences are the same.
From

ξ=(pnξn+ 1 +pn− 1 )/(qnξn+ 1 +qn− 1 )

we obtain

qnξ−pn=(pn− 1 qn−pnqn− 1 )/(qnξn+ 1 +qn− 1 )=(− 1 )n/(qnξn+ 1 +qn− 1 ).

Henceξ>pn/qnifnis even andξ<pn/qnifnis odd. It follows thatpn/qn→ξas
n→∞. Consequently different irrational numbers have different continued fraction
expansions.
Sinceξlies betweenpn/qnandpn+ 1 /qn+ 1 ,wehave

|pn+ 2 /qn+ 2 −pn/qn|<|ξ−pn/qn|<|pn+ 1 /qn+ 1 −pn/qn|.

By( 3 )′and( 4 )′we can rewrite this in the form

an+ 2 /qnqn+ 2 <|ξ−pn/qn|< 1 /qnqn+ 1 (n≥ 0 ). (5)

Hence

q−n+^12 <|qnξ−pn|<qn−+^11 ,

which shows that|qnξ−pn|decreases asnincreases. It follows that|ξ−pn/qn|also
decreases asnincreases.
The rational number pn/qnis called then-thconvergentofξ. The integersan
are called thepartial quotientsand the real numbersξnthecomplete quotientsin the
continued fraction expansion ofξ.
The continued fraction algorithm can be applied also whenξ=ξ 0 is rational, but
in this case it is really the same as the Euclidean algorithm. For supposeξn=bn/cn,