%ComputedEntitiesFile;
]>
Continued Fractions and the Euclidean AlgorithmWilliam F. HammondLecture notes prepared for MATH 326, Spring 1997 Department of Mathematics and Statistics University at AlbanyZGL&TableOfContentsFile;
&SecRef-1;IntroductionContinued fractions offer a means of concrete representation for
arbitrary real numbers The continued fraction expansion of a real
number is an alternative to the representation of such a number as
a (possibly infinite) decimalThe reasons for including this topic in the course on Classical Algebra
are:
&SecRef-2;The continued fraction expansion of a real numberEvery real number x is represented by a point on the real line
and, as such, falls between two integers For example, if n is
an integer and
n x n 1 , x falls between n and n1and there is one and only one
such integer n for any given real x In the case where x
itself is an integer, one has n x The integer n is
sometimes called the floor of xand one often introduces
a notation for the floor of x such as
n [x] Examples:For any real x with $n[x]$ the number
$uxn$ falls in the unit intervalI consisting of all real numbers u for which 0 u 1Thus, for given real x there is a unique decomposition
x n u
where n is an integer and u is in the unit intervalMoreover, u 0 if and only if x is an integer This
decomposition is sometimes called the mod one decomposition
of a real number It is the first step in the process
of expanding x as a continued fractionThe process of finding the continued fraction expansion of a real
number is a recursive process that procedes one step at a timeGiven x one begins with the mod one decomposition
x n1 u1,
where n1 is an integer and 0 u1 1If u1 0which happens if and only if x is an integer,
the recursive process terminates with this first stepThe idea
is to obtain a sequence of integers that give a precise determination
of xIf u1 0then the reciprocal $1u{}_{}$ of u1 satisfies
$1u{}_{}1$ since u1 is in I and, therefore, u1 1
In this case the second step in the recursive determination of the
continued fraction expansion of x is to apply the mod one
decomposition to 1u1 One writes
1u1n2 u2,
where n2 is an integer and 0 u2 1 Combining the
equations that represent the first two steps, one may write
x n11n2 u2Either u2 0in which case the process ends with the
expansion
x n11n2,
or u2 0 In the latter case one does to u2 what had just
been done to u1 above under the assumption u1 0One writes
1u2n3 u3,
where n3 is an integer and 0 u3 1 Then combining
the equations that represent the first three steps, one may write
x n11n21n3 u3After k steps, if the process has gone that far, one has integers
$n{}_{},\; n{}_{},,\; n{}_{}$ and real numbers
$u{}_{},\; u{}_{},,\; u{}_{}$ that are members of the unit interval
I with $u{}_{},\; u{}_{},,\; u{}_{}$ all positive
One may write
x n11n21n311nk uk
Alternatively, one may write
x [ n1, n2, n3, , nk uk ]
If uk 0 the process ends after k steps Otherwise,
the process continues at least one more step with
1uknk1 uk1In this way one associates with any real number x a sequence,
which could be either finite or infinite, $n{}_{},\; n{}_{},$
of integers This sequence is called the continued fraction
expansion ofxAssertLabel-1conventionConventionWhen $[n{}_{},\; n{}_{},\; ...]$ is called a
continued fraction, it is understood that all of the numbers
nj are integers and that $n{}_{}1$ for j 2&SecRef-3;First examples15111 4111 11141 12 341 12 1431 12 11 13[1, 2, 1, 3] 103 111033 11033 16 111033 16 11033 16 16 1[3, 6, 6, 6, ] [2, 3, 5, 2 ] 2 1[3, 5, 2]2 13 1[5, 2]2 13 15 122 13 11122 13 2112 135112 11358135Let
x 11213121312
In this case one finds that
x 1 1y,
where
y 213121312
Further reflection shows that the continued fraction structure for
y is selfsimilar:
y 2131y
This simplifies to
y 7y23y1
and leads to the quadratic equation
3y2 6y 2 0
with discriminant 60Since y 2one of the two
roots of the quadratic equation cannot be yand, therefore,
y 3 153
Finally,
x 1512The idea of the calculation above leads to the conclusion that any
continued fraction $[n{}_{},\; n{}_{},]$ that eventually repeats
is the solution of a quadratic equation with positive discriminant
and integer coefficients The converse of this statement is also
true, but a proof requires further consideration&SecRef-4;The case of a rational numberThe process of finding the continued fraction expansion of a rational
number is essentially identical to the process of applying the
Euclidean algorithm to the pair of integers given by its numerator and
denominatorLet x ab, b 0 be a representation of a rational number
x as a quotient of integers a and b The mod one decomposition
ab n1 u1 , u1a n1 bb
shows that u1 r1bwhere r1 is the remainder for
division of a by b The case where $u{}_{}0$ is the case
where x is an integer Otherwise u1 0and the mod one
decomposition of $1u{}_{}$ gives
br1 n2 u2 , u2b n2 r1r1
This shows that u2 r2r1 where r2 is the remainder for
division of b by r1 Thus, the successive quotients in Euclids
algorithm are the integers $n{}_{},\; n{}_{},$ occurring in the
continued fraction Euclids algorithm terminates after a finite
number of steps with the appearance of a zero remainder Hence, the
continued fraction expansion of every rational number is finiteAssertLabel-2theoremsTheorem1The continued fraction expansion of a real number is
finite if and only if the real number is rationalProof. It has just been shown that if x is rational, then
the continued fraction expansion of x is finite because its calculation
is given by application of the Euclidean algorithm to the numerator
and denominator of x The converse statement is the statement
that every finite continued fraction represents a rational number
That statement will be demonstrated in the following section&SecRef-5;The symbol [t1, t2, , tr]For arbitrary real numbers $t{}_{},\; t{}_{},,\; t{}_{}$
with each $t{}_{}1$ for $j2$
the symbol $[\; t{}_{},\; t{}_{},,\; t{}_{}]$ is defined recursively
by:
[ t1 ] t1t-receqn[t1,t2,,tr ]t11[t2,,tr ]
In order for this definition to make sense one needs to know that
the denominator in the righthand side of (iref="t-rec"t-rec) is nonzero
The condition $t{}_{}1$ for $j2$ guarantees, in
fact, that [t2,,tr ] 0as one may prove using
inductionIt is an easy consequence of mathematical induction that the symbol
$[t{}_{},\; t{}_{},,\; t{}_{}]$ is a rational number if each tj is
rational In particular, each finite continued fraction is a
rational number (Note that the symbol $[t{}_{},\; t{}_{},,\; t{}_{}]$
is to be called a continued fraction, according to the convention of
the first section, only when each tj is an integer.)Observe that the recursive nature of the symbol $[t{}_{},,\; t{}_{}]$
suggests that the symbol should be computed in a particular case working
from right to left Consider again, for example, the computation above
showing that [2, 3, 5, 2] 8135 Working from right to left one
has:
[2] 2 [5, 2]51[2] 512112 [3, 5, 2]31[5, 2] 32113511[2, 3, 5, 2]21[3, 5, 2] 211358135There is, however, another approach to computing
[t1, t2, , tr]
Let, in fact, $t{}_{},\; t{}_{},$ be any (finite or infinite)
sequence of real numbers One uses the double recursion
pdefeqnpj tj pj1 pj2 , j 1 ,
p0 1 , p1 0
to define the sequence pj , j 1 The double
recursion, differently initialized,
qdefeqnqj tj qj1 qj2 , j 1 ,
q0 0 , q1 1
defines the sequence qj , j 1
Note that p1 t1p2 t1t2 1and q1 1 q2 t2q3 t2t3 1One now forms the matrix
Mr-defeqnMjrrpjqjpj1qj1for j 0
Thus, for example,
M0rr1 001 , and
M1rrt1110
It is easy to see that the matrices Mj satisfy the double recursion
Mr-receqnMjrrtj110 Mj1 , j 1
as a consequence of the double recursion formulas for the pj and qj
Hence, a simple argument by mathematical induction shows that
MrcompeqnMrrrtr110rrt2110rrt1110 , r 1
This is summarized by:
AssertLabel-3propositionsProposition1For any sequence $t{}_{},j1$ of
real numbers, if $p{}_{}$ and $q{}_{}$ are the sequences
defined by the double recursions (iref="pdef"pdef) and (iref="qdef"qdef), then one
has the matrix identity
prqr-roweqnrrprqrpr1qr1rrtr110rrt2110rrt1110
for each integer r 1pqidencorollariesCorollary1One has the identity
$p{}_{}q{}_{}q{}_{}p{}_{}(1)r$ for each
integer r 1Proof. The number $p{}_{}q{}_{}q{}_{}p{}_{}$ is the
determinant of the matrix Mr From the formula (iref="Mrcomp"Mrcomp)
the matrix $M{}_{}$ is the product of r matrix factors, each of
which has determinant 1 Since the determinant of the product
of matrices is the product of the determinants of the factors, it is
clear that det(Mr) (1)rvidencorollariesCorollary2One has the vector identity
prqr-veceqnrprqrrrt1110rrt2110rrtr110r1 0
for each integer r 1Proof. First recall (i) that the product of a matrix and a (column)
vector is defined by the relation
rra bcdrx yrax by cx dy, (ii) that the transpose of a matrix is the matrix whose rows
are the columns of the given matrix, and (iii) that the transpose
operation reverses matrix multiplication One tranposes both sides of
the relation (iref="prqr-row"prqr-row) to obtain:
prqr-coleqnrrprpr1qrqr1rrt1110rrt2110rrtr110
To this relation one applies the principle that the first column of
any 2 2 matrix is the product of that matrix with the
column
r1 0
in order to obtain the column identity (iref="prqr-vec"prqr-vec)AssertLabel-6theoremsTheorem2For any sequence $t{}_{},j1$ of
real numbers, if $p{}_{}$ and $q{}_{}$ are the sequences
defined by the double recursions (iref="pdef"pdef) and (iref="qdef"qdef), and
if $t{}_{}1$ for j 2 then the value of the symbol
$[t{}_{},,\; t{}_{}]$ is given by the formula
t-compeqn[t1, t2, , tr] prqrfor r 1 Proof. What is slightly strange about this important
result is that while the $p{}_{}$ and the $q{}_{}$ are
defined by the front end recursions, albeit double recursions,
(iref="pdef"pdef) and (iref="qdef"qdef), the symbol $[t{}_{},,\; t{}_{}]$
is defined by the back end recursion (iref="t-rec"t-rec) The proof
begins with the comment that the righthand side of (iref="t-comp"t-comp)
does not make sense unless one can be sure that the denominator
qr 0 One can show easily by induction on r that
$q{}_{}1$ for $r1$ under the hypothesis $t{}_{}1$
for j 2The proof proceeds by induction on r If r 1the
assertion of the theorem is simply the statement t1 p1q1and, as noted above, $p{}_{}t{}_{}$ and q11 Assume now
that r 2 By induction we may assume the correctness of
the statement (iref="t-comp"t-comp) for symbols of length r1and,
therefore, for the symbol [t2, , tr] That case of the
statement says that $[t{}_{},,\; t{}_{}]$ must be equal to ac
where by corollary iref="viden"videnra crra bcdr1 0
with
rra bcdrrt2110rrtr110
Now by (iref="t-rec"t-rec)
[t1, t2, , tr] t11act1caat1 ca
But by corollary iref="viden"viden again
rprqrrrt1110rra bcdr1 0rrat1 c bt1 dabr1 0rat1 c a
Hence,
prqrat1 ca[t1, t2, , tr] &SecRef-6;Application to Continued FractionsRecall that $[n{}_{},\; n{}_{},]$ is called a continued fraction
only when each nj is an integer and $n{}_{}1$ for j
2The sequence $n{}_{},\; n{}_{},$ may be finite or
infinite The symbol $c{}_{}[n{}_{},\; n{}_{},,\; n{}_{}]$
formed with the first r terms of the sequence, is called the
rthconvergent of the continued fraction
Associated with a given sequence $n{}_{},\; n{}_{},$ are two sequences
$p{}_{},\; p{}_{},$ and $q{}_{},\; q{}_{},$ that are given,
according to the double recursions (iref="pdef"pdef), (iref="qdef"qdef) of the
previous section with tj njAssertLabel-7propositionsProposition2If $[n{}_{},\; n{}_{},]$ is a continued
fraction, then the integers pr and qr are coprime for each
r 1Proof. By Corollary iref="pqiden"pqiden of the previous section
pr qr1 qr pr1 (1)r Hence, any positive
divisor of both pr and qr must divide the lefthand side of
this relation, and, therefore, must also divide (1)rAssertLabel-8propositionsProposition3The difference between successive convergents
of the continued fraction $[n{}_{},\; n{}_{},]$ is given by
the formula
convgtdiffeqncr cr1(1)rqr qr1for
r 2 Proof. According to the theorem (formula iref="t-comp"t-comp) at the
end of the last section the convergent cr is given by
crprqr
Hence,
cr cr1prqrpr1qr1pr qr1 pr1 qrqr qr1(1)rqr qr1
(The last step is by Corollary iref="pqiden"pqiden above.)
AssertLabel-9remarksRemark1The formula (iref="convgtdiff"convgtdiff) remains true if
$c{}_{}[t{}_{},,\; t{}_{}]$ where the tj are real numbers
subject to the assumption $t{}_{}1$ for j 1AssertLabel-10AssertDefaultLemmaThe sequence $q{}_{}$ is a strictly
increasing sequence for j 2Proof. This is easily proved by induction from the recursive
definition (iref="qdef"qdef) of the sequenceAssertLabel-11theoremsTheorem3If $[n{}_{},\; n{}_{},]$ is an infinite
continued fraction, then the limit
limr prqr
always existsProof. As one plots the convergents cr on the line of real
numbers, one moves alternately right and left The formula
(iref="convgtdiff"convgtdiff) for the difference between successive convergents
elucidates not only the fact of alternate right and left movement but
also the fact that each successive movement is smaller than the one
preceding Therefore, one has
c1 c3 c5 c6 c4 c2
Since any strictly increasing sequence of positive integers
must have infinite limit, the seqence $q{}_{}q{}_{}$ has infinite
limit, and so the sequence of reciprocals $1q{}_{}q{}_{}$ must
converge to zero Hence, the sequences of odd and evenindexed
convergents must have the same limit, which is the limit of the
sequence of all convergentsAssertLabel-12definitionsDefinition1The limit of the sequence of convergents of an
infinite continued fraction is called the value of that
continued fractionAssertLabel-13theoremsTheorem4If $[n{}_{},\; n{}_{},]$ is the continued
fraction expansion of an irrational number xthen
x limr prqr;
that is, the value of the continued fraction expansion of a real
number is that real numberProof. For each $r1$ the continued fraction expansion
$[n{}_{},\; n{}_{},]$ of x is characterized by the identity
xconfraceqnx [n1, n2, , nr ur] ,
where ur is a real number with 0 ur 1
The sequences of ps and qs for the symbol
$[n{}_{},\; n{}_{},,\; n{}_{}u{}_{}]$ agree with those for the symbol
$[n{}_{},\; n{}_{},,\; n{}_{}]$ except for the rth terms
One has by (iref="t-comp"t-comp)
[n1, n2, , nr ur] PrQr,
where by (iref="qdef"qdef)
qrnr qr1 qr2 Qr(nr ur) qr1 qr2
Hence,
Qrqr ur qr1
Therefore, the displacement from cr1 to x is by (iref="convgtdiff"convgtdiff)
(1)rQr qr1(1)r(qr qr1 ur qr12),
which is in the same direction but of smaller magnitude than the
displacement from cr1 to cr Therefore, x must be larger
than every oddindexed convergent and smaller than every evenindexed
convergent But since all convergents have the same limit, that limit
must be x&SecRef-7;Bezouts Identity and the double recursionIt has already been observed that the process of finding the continued
fraction expansion of a rational number ab (b 0), involves
the same series of long divisions that are used in the application of
the Euclidean algorithm to the pair of integers a and b Recall
that at each stage in the Euclidean algorithm the divisor for the current
stage is the remainder from the previous stage and the dividend for the
current stage is the divisor from the previous stage, or, equivalently,
the dividend for the current stage is the remainder from the second
previous stage The Euclidean algorithm may thus be viewed as a double
recursion that is used to construct the sequence of remainders One
starts the double recursion with
r1 a and r0 b
At the jth stage one performs long division of rj2
by rj1 to obtain the integer quotient nj and the integer
remainder rj that satisfies 0 rj rj1 Thus,
remreceqnrjrj2 nj rj1
The Euclidean algorithm admits an additional stage if rj 0
Since
0 rj rj1 r2 r1 r0 b ,
there can be at most b stagesOne may use the sequence of successive quotients nj (j 1)
to form sequences $p{}_{}$ and qj as in the
previous section, according to the double recursions:
npdefeqnpj nj pj1pj2 ,j 1 ;p0 1 ,p1 0 nqdefeqnqj nj qj1qj2 ,j 1 ;q0 0 ,q1 1
It has already been observed that $q{}_{}1$ for $j1$ and
[n1, n2,, nj]pjqj ,j 1 Bezouts Identity says not only that the greatest common divisor of a
and b is an integer linear combination of them but that the coefficents
in that integer linear combination may be taken, up to a sign, as q
and pAssertLabel-14theoremsTheorem5If the application of the Euclidean algorithm to
a and b (b 0) ends with the mth long division,
i.e., rm 0then
bezouteqnrj(1)j1qj a pj b , 1 j m Proof. One uses induction on jFor $j1$ the statement
is r1 q1 a p1 b Since by (iref="npdef"npdef, iref="nqdef"nqdef)
$q{}_{}1$ and p1 n1this statement is simply the
case $j1$ in (iref="remrec"remrec) Assume j 2 and that
the formula (iref="bezout"bezout) has been established for indices smaller than
j By (iref="remrec"remrec) one has
rjrj2 nj rj1
In this equation one may use (iref="bezout"bezout) to expand the terms
rj2 and rj1 to obtain:
rj(1)j3(qj2a pj2b)
nj(1)j2(qj1a pj1b) (1)j1(qj2a pj2b)
nj(1)j1(qj1a pj1b) (1)j1(qj2a pj2b)
nj (qj1a pj1b) (1)j1(qj2 nj qj1)a
(pj2 nj pj1)b (1)j1qj a pj b AssertLabel-15corollariesCorollary3The greatest common divisor d of a and b
is given by the formula
gcdbezouteqnd (1)m (qm1a pm1 b) ,
where m is the number of divisions required to obtain zero
remainder in the Euclidean algorithmProof. One knows that d is the last nonzero remainder
rm1 in the Euclidean algorithm This formula for d is the
case $jm1$ in (iref="bezout"bezout)AssertLabel-16corollariesCorollary4checkbezouteqnpmad , qmbdProof. The last remainder rm 0 The case $jm$
in (iref="bezout"bezout) shows that ab pmqm Since, by the first
proposition of the preceding section, pm and qm have no common
factor, this corollary is evident&SecRef-8;The action of $GL{}_{}(Z)$ on the projective lineIf abcd are real
numbers with $adbc0$and
M rra bcd
is the matrix with entries abcand d
then M z for z real, will denote the expression
glacteqnM z a z bc z d
One calls $Mz$ the action of M on z$Mz$ is a perfectly good function of z except for
the case $zdc$ where the denominator $czd$ vanishes
If it were also true that $azb0$ for the same z then
one would have ba dc in contradiction of the assumption
ad bc 0 Thus, when z dc the
value of M w increases beyond all bounds as w approaches z
and it is convenient to say that
M dc
where is regarded as large and signless If further it is agreed
to define
M ac ,
which is the limiting value of $Mw$ as w increases
without bound, then one may regard the expression $Mz$
as being defined always for all real z and for The set
consisting of all real numbers and also the object (not a number)
is called the projective line The projective line is
therefore the union of the (ordinary) affine line with a single point
AssertLabel-17propositionsProposition4If $[n{}_{},\; n{}_{},]$ is any continued
fraction, then
cfgleqn[n1, n2, , nr, nr1, ] M [nr1, ]
where
M rrn1110rrnr110Proof. Let z [nr1, ] Then
[n1, n2, , nr, nr1, ] [n1, n2, , nr, z ]
The statement of the proposition now becomes
[n1, n2, , nr, z ] M z
This may be seen to follow by multiplying both sides in formula
(iref="prqr-col"prqr-col), after replacing tj with nj, by the column
rz 1The matrix M in the preceding proposition is an integer matrix with
determinant 1 The notation $GL{}_{}(Z)$ denotes the set
of all such matrices (The 2 indicates the size of the matrices,
and the Z indicates that the entries in such matrices are numbers
in the set Z of integers.) It is easy to check that the product of
two members of $GL{}_{}(Z)$ is a member of $GL{}_{}(Z)$ and
that the matrix inverse of a member of $GL{}_{}(Z)$ is a member
of GL2(Z) Thus, $GL{}_{}(Z)$ forms what is called
a group The formula (iref="glact"glact) defines what is called the
action of $GL{}_{}(Z)$ on the projective lineOne says that two points z and w of the projective line are
rationally equivalent if there is a matrix M in $GL{}_{}(Z)$
for which w M z Since (i) $GL{}_{}(Z)$ is a group,
(ii) M1 (M2 z) (M1 M2) z and (iii)
$wMz$ if and only z M1 w it is easy to
see that every point of the projective line belongs to one and only one
rational equivalence class and that two points rationally equivalent to
a third must be rationally equivalent to each otherAssertLabel-18AssertDefaultTerminologyThe rational equivalence of points
on the projective line is said to be the equivalence relation on the
projective line defined by the action of GL2(Z)AssertLabel-19examplesExample1The set of real numbers rationally equivalent to
the point is precisely the set of rational numbersAssertLabel-20examplesExample2The proposition above shows that any continued
fraction is rationally equivalent to each of its tails It follows that
all tails of a continued fraction are rationally equivalent to each
other&SecRef-9;Periodic continued fractionsIn one of the first examples of a continued fraction expansion, it was
shown that 10 [3,6,6,6,] This is an example of
a periodic continued fraction After a finite number of terms
the sequence of integers repeats cyclically If a cyclic pattern is
present from the very first term, then the continued fraction is called
purely periodic Evidently, $[6,6,6,]103$
is an example of a purely periodic continued fractionNote that a periodic continued fraction cannot represent a rational
number since the continued fraction expansion of a rational number is
finiteAssertLabel-21theoremsTheorem6Every periodic continued fraction is the continued
fraction expansion of a real quadratic irrational numberProof. For clarity: it is being asserted that every periodic
continued fraction represent a number of the form
a bmc
where abc and m are all integers with m 0c 0 and m not a perfect squareNumbers of this form with fixed m but varying integers ab and $c0$ may be added, subtracted, multiplied, and
divided without leaving the class of such numbers (The statement
here about division becomes clear if one remembers always to
rationalize denominators.) Consequently, for M in
$GL{}_{}(Z)$ the number $Mz$ will be a number of this
form or if and only if z is in the same classSince a periodic continued fraction is rationally equivalent to a
purely periodic continued fraction, the question of whether any
periodic continued fraction is a quadratic irrationality reduces to
the question of whether a purely periodic continued fraction is such
Let
x [n1, , nr, n1, , nr, n1, , nr, ]
be a purely periodic continued fraction By the proposition of the
preceding section, $xMx$ where M is notationally
identical to the M in (iref="cfgl"cfgl) Ignoring the computation
(iref="prqr-col"prqr-col) of M in terms of convergents, let
M rra bcd
Then
x ax bcx d,
or, otherwise said, x is a solution of the quadratic equation
cx2 (ad) x b 0 AssertLabel-22remarksRemark2It is conversely true that the continued fraction expansion of every
real quadratic irrationality is periodicThis converse will not be proved here&BibRef-KEY-1;KEY-1 G. Chrystal, Algebra: An Elementary Textbook (2 vols.),
Chelsea&BibRef-KEY-2;KEY-2 G. Hardy E. Wright, An Introduction to the Theory
of Numbers, Oxford Univ. Press&BibRef-KEY-3;KEY-3 S. Lang, Introduction to Diophantine Approximations,
AddisonWesley&BibRef-KEY-4;KEY-4 O. Perron, Die Lehre von den Kettenbruchen, 2nd ed.,
Chelsea