IV Continued Fractions and Their Uses............................
1 TheContinuedFractionAlgorithm.............................
Letξ=ξ 0 be an irrational real number. Then we can write
ξ 0 =a 0 +ξ 1 −^1 ,wherea 0 = ξ 0 is the greatest integer≤ξ 0 and whereξ 1 >1 is again an irrational
number. Hence the process can be repeated indefinitely:
ξ 1 =a 1 +ξ 2 −^1 ,(a 1 = ξ 1 ,ξ 2 > 1 ),
ξ 2 =a 2 +ξ 3 −^1 ,(a 2 = ξ 2 ,ξ 3 > 1 ),
···By construction,an∈Zfor alln≥0andan≥1ifn≥1. The uniquely determined
infinite sequence [a 0 ,a 1 ,a 2 ,...] is called thecontinued fraction expansionofξ.The
continued fraction expansion ofξnis [an,an+ 1 ,an+ 2 ,...].
For example, the ‘golden ratio’τ = ( 1 +
√
5 )/2 has the continued fraction
expansion [1, 1 , 1 ,...], sinceτ= 1 +τ−^1. Similarly,
√
2 has the continued fraction
expansion [1, 2 , 2 ,...], since
√
2 + 1 = 2 + 1 /(
√
2 + 1 ).
The relation betweenξnandξn+ 1 may be written as a linear fractional transforma-
tion:
ξn=(anξn+ 1 + 1 )/( 1 ξn+ 1 + 0 ).An arbitrary linear fractional transformation
ξ=(αξ′+β)/(γξ′+δ)is completely determined by its matrix
T=
(
αβ
γδ)
.
This description is convenient, because if we make a further linear fractional transfor-
mation
ξ′=(α′ξ′′+β′)/(γ′ξ′′+δ′)W.A. Coppel, Number Theory: An Introduction to Mathematics, Universitext,
DOI: 10.1007/978-0-387-89486-7_4, © Springer Science + Business Media, LLC 2009
179