Continued Fractions and the Euclidean

Algorithm
Lecture notes prepared for MATH 326, Spring 1997
Department of Mathematics and Statistics
University at Albany
William F. Hammond
Table of Contents
1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 The continued fraction expansion of a real number . . . . . . . . . . . . . . . . . . . . 2
3 First examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 The case of a rational number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5 The symbol [t
1
, t
2
, . . . , t
r
] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
6 Application to Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7 Bezouts Identity and the double recursion. . . . . . . . . . . . . . . . . . . . . . . . . . . 11
8 The action of GL
2
(Z) on the projective line . . . . . . . . . . . . . . . . . . . . . . . . . 13
9 Periodic continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1 Introduction
Continued fractions oer 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 innite) decimal.
The reasons for including this topic in the course on Classical Algebra are:
(i) The subject provides many applications of the method of recursion.
(ii) It is closely related to the Euclidean algorithm and, in particular, to Bezouts Identity.
(iii) It provides an opportunity to introduce the subject of group theory via the 2-dimensional
unimodular group GL
2
(Z).
2 The continued fraction expansion of a real number
Every 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 n +1, and 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
oor of x, and one often introduces a notation for the oor of x such as
n = [x] .
Examples:
1.
2 = [1.5]
2.
3 = []
For any real x with n = [x] the number u = x n falls in the unit interval I consisting of
all real numbers u for which 0 u < 1.
Thus, for given real x there is a unique decomposition
x = n + u
where n is an integer and u is in the unit interval. Moreover, 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 rst step in the process of expanding x as a continued fraction.
The process of nding the continued fraction expansion of a real number is a recursive process
that procedes one step at a time. Given x one begins with the mod one decomposition
x = n
1
+ u
1
,
where n
1
is an integer and 0 u
1
< 1.
If u
1
= 0, which happens if and only if x is an integer, the recursive process terminates with
this rst step. The idea is to obtain a sequence of integers that give a precise determination
of x.
If u
1
> 0, then the reciprocal 1/u
1
of u
1
satises 1/u
1
> 1 since u
1
is in I and, therefore,
u
1
< 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 1/u
1
. One writes
1/u
1
= n
2
+ u
2
,
where n
2
is an integer and 0 u
2
< 1. Combining the equations that represent the rst two
steps, one may write
x = n
1
+
1
n
2
+ u
2
.
2
Either u
2
= 0, in which case the process ends with the expansion
x = n
1
+
1
n
2
,
or u
2
> 0. In the latter case one does to u
2
what had just been done to u
1
above under the
assumption u
1
> 0. One writes
1/u
2
= n
3
+ u
3
,
where n
3
is an integer and 0 u
3
< 1. Then combining the equations that represent the rst
three steps, one may write
x = n
1
+
1
n
2
+
1
n3+u3
.
After k steps, if the process has gone that far, one has integers n
1
, n
2
, . . . , n
k
and real numbers
u
1
, u
2
, . . . , u
k
that are members of the unit interval I with u
1
, u
2
, . . . , u
k1
all positive. One
may write
x = n
1
+
1
n
2
+
1
n3+
1
...+
1
n
k
+u
k
.
Alternatively, one may write
x = [n
1
, n
2
, n
3
, . . . , n
k
+ u
k
] .
If u
k
= 0, the process ends after k steps. Otherwise, the process continues at least one more
step with
1/u
k
= n
k+1
+ u
k+1
.
In this way one associates with any real number x a sequence, which could be either nite or
innite, n
1
, n
2
, . . . of integers. This sequence is called the continued fraction expansion of x.
Convention. When [n
1
, n
2
, ...] is called a continued fraction, it is understood that all of the
numbers n
j
are integers and that n
j
1 for j 2.
3
3 First examples
15
11
= 1 +
4
11
= 1 +
1
11
4
= 1 +
1
2 +
3
4
= 1 +
1
2 +
1
4
3
= 1 +
1
2 +
1
1+
1
3
= [1, 2, 1, 3] .

10 = 3 +
1
1

103
= 3 +
1

10 + 3
= 3 +
1
6 +
1
1

103
= 3 +
1
6 +
1

10+3
= 3 +
1
6 +
1
6+
1
...
= [3, 6, 6, 6, . . . ] .
4
[2, 3, 5, 2] = 2 +
1
[3, 5, 2]
= 2 +
1
3 +
1
[5,2]
= 2 +
1
3 +
1
5+
1
2
= 2 +
1
3 +
1
11
2
= 2 +
1
3 +
2
11
= 2 +
1
35
11
= 2 +
11
35
=
81
35
.
Let
x = 1 +
1
2 +
1
3+
1
2+
1
3+
1
2+...
.
In this case one nds that
x = 1 +
1
y
,
where
y = 2 +
1
3 +
1
2+
1
3+
1
2+...
.
Further reection shows that the continued fraction structure for y is self-similar:
y = 2 +
1
3 +
1
y
.
This simplies to
y =
7y + 2
3y + 1
and leads to the quadratic equation
3y
2
6y 2 = 0
with discriminant 60. Since y > 2, one of the two roots of the quadratic equation cannot be
y, and, therefore,
y =
3 +

15
3
.
5
Finally,
x =

15 1
2
.
The idea of the calculation above leads to the conclusion that any continued fraction [n
1
, n
2
, . . . ]
that eventually repeats is the solution of a quadratic equation with positive discriminant and
integer coecients. The converse of this statement is also true, but a proof requires further
consideration.
4 The case of a rational number
The process of nding 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 denominator.
Let x = a/b, b > 0, be a representation of a rational number x as a quotient of integers a and
b. The mod one decomposition
a
b
= n
1
+ u
1
, u
1
=
a n
1
b
b
shows that u
1
= r
1
/b, where r
1
is the remainder for division of a by b. The case where
u
1
= 0 is the case where x is an integer. Otherwise u
1
> 0, and the mod one decomposition
of 1/u
1
gives
b
r
1
= n
2
+ u
2
, u
2
=
b n
2
r
1
r
1
.
This shows that u
2
= r
2
/r
1
, where r
2
is the remainder for division of b by r
1
. Thus, the
successive quotients in Euclids algorithm are the integers n
1
, n
2
, . . . occurring in the continued
fraction. Euclids algorithm terminates after a nite number of steps with the appearance of a
zero remainder. Hence, the continued fraction expansion of every rational number is nite.
Theorem 1. The continued fraction expansion of a real number is nite if and only if the real
number is rational.
Proof. It has just been shown that if x is rational, then the continued fraction expansion of x is
nite 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 nite continued
fraction represents a rational number. That statement will be demonstrated in the following
section.
5 The symbol [t
1
, t
2
, . . . , t
r
]
For arbitrary real numbers t
1
, t
2
, . . . , t
r
with each t
j
1 for j 2 the symbol [t
1
, t
2
, . . . , t
r
]
is dened recursively by:
[t
1
] = t
1
6
[t
1
, t
2
, . . . , t
r
] = t
1
+
1
[t
2
, . . . , t
r
]
. (1)
In order for this denition to make sense one needs to know that the denominator in the
right-hand side of (1) is non-zero. The condition t
j
1 for j 2 guarantees, in fact, that
[t
2
, . . . , t
r
] > 0, as one may prove using induction.
It is an easy consequence of mathematical induction that the symbol [t
1
, t
2
, . . . , t
r
] is a rational
number if each t
j
is rational. In particular, each nite continued fraction is a rational number.
(Note that the symbol [t
1
, t
2
, . . . , t
r
] is to be called a continued fraction, according to the
convention of the rst section, only when each t
j
is an integer.)
Observe that the recursive nature of the symbol [t
1
, . . . , t
r
] 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] = 81/35. Working from right to left one has:
[2] = 2
[5, 2] = 5 +
1
[2]
= 5 +
1
2
=
11
2
[3, 5, 2] = 3 +
1
[5, 2]
= 3 +
2
11
=
35
11
[2, 3, 5, 2] = 2 +
1
[3, 5, 2]
= 2 +
11
35
=
81
35
There is, however, another approach to computing [t
1
, t
2
, . . . , t
r
]. Let, in fact, t
1
, t
2
, . . . be
any (nite or innite) sequence of real numbers. One uses the double recursion
p
j
= t
j
p
j1
+ p
j2
, j 1 , p
0
= 1 , p
1
= 0 (2)
to dene the sequence {p
j
} , j 1. The double recursion, dierently initialized,
q
j
= t
j
q
j1
+ q
j2
, j 1 , q
0
= 0 , q
1
= 1 (3)
denes the sequence {q
j
} , j 1. Note that p
1
= t
1
, p
2
= t
1
t
2
+ 1, . . . and q
1
= 1,
q
2
= t
2
, q
3
= t
2
t
3
+ 1, . . . .
One now forms the matrix
M
j
=

p
j
q
j
p
j1
q
j1

for j 0 . (4)
Thus, for example,
M
0
=

1 0
0 1

, and M
1
=

t
1
1
1 0

.
It is easy to see that the matrices M
j
satisfy the double recursion
M
j
=

t
j
1
1 0

M
j1
, j 1 (5)
7
as a consequence of the double recursion formulas for the p
j
and q
j
. Hence, a simple argument
by mathematical induction shows that
M
r
=

t
r
1
1 0

. . .

t
2
1
1 0

t
1
1
1 0

, r 1 . (6)
This is summarized by:
Proposition 1. For any sequence {t
j
}, j 1 of real numbers, if {p
j
} and {q
j
} are the
sequences dened by the double recursions (2) and (3), then one has the matrix identity

p
r
q
r
p
r1
q
r1

t
r
1
1 0

. . .

t
2
1
1 0

t
1
1
1 0

(7)
for each integer r 1.
Corollary 1. One has the identity p
r
q
r1
q
r
p
r1
= (1)
r
for each integer r 1.
Proof. The number p
r
q
r1
q
r
p
r1
is the determinant of the matrix M
r
. From the formula
(6) the matrix M
r
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(M
r
) = (1)
r
.
Corollary 2. One has the vector identity

p
r
q
r

t
1
1
1 0

t
2
1
1 0

. . .

t
r
1
1 0

1
0

(8)
for each integer r 1.
Proof. First recall (i) that the product of a matrix and a (column) vector is dened by the
relation

a b
c d

x
y

ax + 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 (7) to obtain:

p
r
p
r1
q
r
q
r1

t
1
1
1 0

t
2
1
1 0

. . .

t
r
1
1 0

. (9)
To this relation one applies the principle that the rst column of any 22 matrix is the product
of that matrix with the column

1
0

in order to obtain the column identity (8).

Theorem 2. For any sequence {t
j
}, j 1 of real numbers, if {p
j
} and {q
j
} are the sequences
dened by the double recursions (2) and (3), and if t
j
1 for j 2, then the value of the
symbol [t
1
, . . . , t
r
] is given by the formula
[t
1
, t
2
, . . . , t
r
] =
p
r
q
r
for r 1 . (10)
8
Proof. What is slightly strange about this important result is that while the {p
r
} and the
{q
r
} are dened by the front end recursions, albeit double recursions, (2) and (3), the symbol
[t
1
, . . . , t
r
] is dened by the back end recursion (1). The proof begins with the comment that
the right-hand side of (10) does not make sense unless one can be sure that the denominator
q
r
= 0. One can show easily by induction on r that q
r
1 for r 1 under the hypothesis
t
j
1 for j 2.
The proof proceeds by induction on r. If r = 1, the assertion of the theorem is simply the
statement t
1
= p
1
/q
1
, and, as noted above, p
1
= t
1
and q
1
= 1. Assume now that r 2.
By induction we may assume the correctness of the statement (10) for symbols of length r 1,
and, therefore, for the symbol [t
2
, . . . , t
r
]. That case of the statement says that [t
2
, . . . , t
r
]
must be equal to a/c , where by corollary 2

a
c

a b
c d

1
0

with

a b
c d

t
2
1
1 0

. . .

t
r
1
1 0

.
Now by (1)
[t
1
, t
2
, . . . , t
r
] = t
1
+
1
a/c
= t
1
+
c
a
=
at
1
+ c
a
.
But by corollary 2 again

p
r
q
r

t
1
1
1 0

a b
c d

1
0

at
1
+ c bt
1
+ d
a b

1
0

at
1
+ c
a

.
Hence,
p
r
q
r
=
at
1
+ c
a
= [t
1
, t
2
, . . . , t
r
] .
6 Application to Continued Fractions
Recall that [n
1
, n
2
, . . . ] is called a continued fraction only when each n
j
is an integer and
n
j
1 for j 2. The sequence n
1
, n
2
, . . . may be nite or innite. The symbol c
r
=
[n
1
, n
2
, . . . , n
r
] formed with the rst r terms of the sequence, is called the r
th
convergent of the
continued fraction. Associated with a given sequence n
1
, n
2
, . . . are two sequences p
1
, p
2
, . . .
and q
1
, q
2
, . . . that are given, according to the double recursions (2), (3) of the previous section
with t
j
= n
j
.
Proposition 2. If [n
1
, n
2
, . . . ] is a continued fraction, then the integers p
r
and q
r
are coprime
for each r 1.
Proof. By Corollary 1 of the previous section p
r
q
r1
q
r
p
r1
= (1)
r
. Hence, any positive
divisor of both p
r
and q
r
must divide the left-hand side of this relation, and, therefore, must
also divide (1)
r
.
9
Proposition 3. The dierence between successive convergents of the continued fraction [n
1
, n
2
, . . . ]
is given by the formula
c
r
c
r1
=
(1)
r
q
r
q
r1
for r 2 . (11)
Proof. According to the theorem (formula 10) at the end of the last section the convergent c
r
is given by
c
r
=
p
r
q
r
.
Hence,
c
r
c
r1
=
p
r
q
r

p
r1
q
r1
=
p
r
q
r1
p
r1
q
r
q
r
q
r1
=
(1)
r
q
r
q
r1
.
(The last step is by Corollary 1 above.)
Remark 1. The formula (11) remains true if c
r
= [t
1
, . . . , t
r
] where the t
j
are real numbers
subject to the assumption t
j
1 for j 1.
Lemma. The sequence {q
j
} is a strictly increasing sequence for j 2.
Proof. This is easily proved by induction from the recursive denition (3) of the sequence.
Theorem 3. If [n
1
, n
2
, . . . ] is an innite continued fraction, then the limit
lim
r
p
r
q
r
always exists.
Proof. As one plots the convergents c
r
on the line of real numbers, one moves alternately right
and left. The formula (11) for the dierence 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
c
1
< c
3
< c
5
< . . . < c
6
< c
4
< c
2
.
Since any strictly increasing sequence of positive integers must have innite limit, the seqence
q
j
q
j1
has innite limit, and so the sequence of reciprocals 1/q
j
q
j1
must converge to zero.
Hence, the sequences of odd- and even-indexed convergents must have the same limit, which is
the limit of the sequence of all convergents.
Denition 1. The limit of the sequence of convergents of an innite continued fraction is called
the value of that continued fraction.
10
Theorem 4. If [n
1
, n
2
, . . . ] is the continued fraction expansion of an irrational number x, then
x = lim
r
p
r
q
r
;
that is, the value of the continued fraction expansion of a real number is that real number.
Proof. For each r 1 the continued fraction expansion [n
1
, n
2
, . . . ] of x is characterized by
the identity
x = [n
1
, n
2
, . . . , n
r
+ u
r
] , (12)
where u
r
is a real number with 0 u
r
< 1. The sequences of ps and qs for the symbol
[n
1
, n
2
, . . . , n
r
+ u
r
] agree with those for the symbol [n
1
, n
2
, . . . , n
r
] except for the r
th
terms.
One has by (10)
[n
1
, n
2
, . . . , n
r
+ u
r
] =
P
r
Q
r
,
where by (3)
q
r
= n
r
q
r1
+ q
r2
Q
r
= (n
r
+ u
r
)q
r1
+ q
r2
Hence,
Q
r
= q
r
+ u
r
q
r1
.
Therefore, the displacement from c
r1
to x is by (11)
(1)
r
Q
r
q
r1
=
(1)
r
(q
r
q
r1
+ u
r
q
2
r1
)
,
which is in the same direction but of smaller magnitude than the displacement from c
r1
to
c
r
. Therefore, x must be larger than every odd-indexed convergent and smaller than every
even-indexed convergent. But since all convergents have the same limit, that limit must be x.
7 Bezouts Identity and the double recursion
It has already been observed that the process of nding the continued fraction expansion of a
rational number a/b (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
r
1
= a and r
0
= b .
At the j
th
stage one performs long division of r
j2
by r
j1
to obtain the integer quotient n
j
and the integer remainder r
j
that satises 0 r
j
< r
j1
. Thus,
r
j
= r
j2
n
j
r
j1
. (13)
11
The Euclidean algorithm admits an additional stage if r
j
> 0. Since
0 r
j
< r
j1
< . . . < r
2
< r
1
< r
0
= b ,
there can be at most b stages.
One may use the sequence of successive quotients n
j
(j 1) to form sequences {p
j
} and {q
j
},
as in the previous section, according to the double recursions:
p
j
= n
j
p
j1
+ p
j2
, j 1 ; p
0
= 1 , p
1
= 0 . (14)
q
j
= n
j
q
j1
+ q
j2
, j 1 ; q
0
= 0 , q
1
= 1 . (15)
It has already been observed that q
j
1 for j 1 and
[n
1
, n
2
, . . . , n
j
] =
p
j
q
j
, 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 coecents in that integer linear combination may be taken,
up to a sign, as q and p.
Theorem 5. If the application of the Euclidean algorithm to a and b (b > 0) ends with the
m
th
long division, i.e., r
m
= 0, then
r
j
= (1)
j1
(q
j
a p
j
b) , 1 j m . (16)
Proof. One uses induction on j. For j = 1 the statement is r
1
= q
1
a p
1
b. Since by (14,
15) q
1
= 1 and p
1
= n
1
, this statement is simply the case j = 1 in (13). Assume j 2,
and that the formula (16) has been established for indices smaller than j. By (13) one has
r
j
= r
j2
n
j
r
j1
.
In this equation one may use (16) to expand the terms r
j2
and r
j1
to obtain:
r
j
=

(1)
j3
(q
j2
a p
j2
b)

n
j

(1)
j2
(q
j1
a p
j1
b)

=

(1)
j1
(q
j2
a p
j2
b)

+ n
j

(1)
j1
(q
j1
a p
j1
b)

= (1)
j1
{(q
j2
a p
j2
b) + n
j
(q
j1
a p
j1
b)}
= (1)
j1
{(q
j2
+ n
j
q
j1
)a (p
j2
+ n
j
p
j1
)b}
= (1)
j1
{q
j
a p
j
b} .
Corollary 3. The greatest common divisor d of a and b is given by the formula
d = (1)
m
(q
m1
a p
m1
b) , (17)
where m is the number of divisions required to obtain zero remainder in the Euclidean algorithm.
12
Proof. One knows that d is the last non-zero remainder r
m1
in the Euclidean algorithm. This
formula for d is the case j = m1 in (16).
Corollary 4.
p
m
=
a
d
, q
m
=
b
d
. (18)
Proof. The last remainder r
m
= 0. The case j = m in (16) shows that a/b = p
m
/q
m
.
Since, by the rst proposition of the preceding section, p
m
and q
m
have no common factor, this
corollary is evident.
8 The action of GL
2
(Z) on the projective line
If a, b, c, d are real numbers with ad bc = 0 and
M =

a b
c d

is the matrix with entries a, b, c, and d, then M z, for z real, will denote the expression
M z =
az + b
cz + d
. (19)
One calls M z the action of M on z.
M z is a perfectly good function of z except for the case z = d/c where the denominator
cz + d vanishes. If it were also true that az + b = 0 for the same z, then one would have
b/a = d/c, in contradiction of the assumption ad bc = 0. Thus, when z = d/c, the
value of |M w| increases beyond all bounds as w approaches z, and it is convenient to say that
M

d
c

=
where is regarded as large and signless. If further it is agreed to dene
M =
a
c
,
which is the limiting value of M w as |w| increases without bound, then one may regard the
expression M z as being dened 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) ane line with a single point .
Proposition 4. If [n
1
, n
2
, . . . ] is any continued fraction, then
[n
1
, n
2
, . . . , n
r
, n
r+1
, . . . ] = M [n
r+1
, . . . ] . (20)
where
M =

n
1
1
1 0

. . .

n
r
1
1 0

.
13
Proof. Let z = [n
r+1
, . . . ]. Then
[n
1
, n
2
, . . . , n
r
, n
r+1
, . . . ] = [n
1
, n
2
, . . . , n
r
, z] .
The statement of the proposition now becomes
[n
1
, n
2
, . . . , n
r
, z] = M z .
This may be seen to follow by multiplying both sides in formula (9), after replacing t
j
with n
j
,
by the column

z
1

.
The matrix M in the preceding proposition is an integer matrix with determinant 1. The
notation GL
2
(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
2
(Z) is a member of GL
2
(Z) and that
the matrix inverse of a member of GL
2
(Z) is a member of GL
2
(Z). Thus, GL
2
(Z) forms
what is called a group. The formula (19) denes what is called the action of GL
2
(Z) on the
projective line.
One says that two points z and w of the projective line are rationally equivalent if there is a
matrix M in GL
2
(Z) for which w = M z. Since (i) GL
2
(Z) is a group, (ii) M
1
(M
2
z) =
(M
1
M
2
) z, and (iii) w = M z if and only z = M
1
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 other.
Terminology. The rational equivalence of points on the projective line is said to be the equiv-
alence relation on the projective line dened by the action of GL
2
(Z).
Example 1. The set of real numbers rationally equivalent to the point is precisely the set
of rational numbers.
Example 2. The 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.
9 Periodic continued fractions
In one of the rst 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 nite number of
terms the sequence of integers repeats cyclically. If a cyclic pattern is present from the very rst
term, then the continued fraction is called purely periodic. Evidently, [6, 6, 6, . . . ] =

10 3
is an example of a purely periodic continued fraction.
Note that a periodic continued fraction cannot represent a rational number since the continued
fraction expansion of a rational number is nite.
14
Theorem 6. Every periodic continued fraction is the continued fraction expansion of a real
quadratic irrational number.
Proof. For clarity: it is being asserted that every periodic continued fraction represent a number
of the form
a + b

m
c
where a, b, c, and m are all integers with m > 0, c = 0, and m not a perfect square.
Numbers of this form with xed m but varying integers a, b, and c = 0 may be added, sub-
tracted, multiplied, and divided without leaving the class of such numbers. (The statement
here about division becomes clear if one remembers always to rationalize denominators.) Con-
sequently, for M in GL
2
(Z) the number M z will be a number of this form or if and only
if z is in the same class.
Since a periodic continued fraction is rationally equivalent to a purely periodic continued frac-
tion, 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 = [n
1
, . . . , n
r
, n
1
, . . . , n
r
, n
1
, . . . , n
r
, . . . ]
be a purely periodic continued fraction. By the proposition of the preceding section, x = M x
where M is notationally identical to the M in (20). Ignoring the computation (9) of M in
terms of convergents, let
M =

a b
c d

.
Then
x =
ax + b
cx + d
,
or, otherwise said, x is a solution of the quadratic equation
cx
2
(a d)x b = 0 .
Remark 2. It is conversely true that the continued fraction expansion of every real quadratic
irrationality is periodic.
This converse will not be proved here.
References
[1] G. Chrystal, Algebra: An Elementary Textbook (2 vols.), Chelsea.
[2] G. Hardy & E. Wright, An Introduction to the Theory of Numbers, Oxford Univ. Press.
[3] S. Lang, Introduction to Diophantine Approximations, Addison-Wesley.
[4] O. Perron, Die Lehre von den Kettenbr uchen, 2nd ed., Chelsea.
15