Continued Fractions

Darren C. Collins

Abstract. In this paper, we discuss continued fractions. First, we discuss the definition
and notation. Second, we discuss the development of the subject throughout history.
Third, we recall some theory of continued fractions. Finally, we use the theory to examine
applications of continued fractions.

1. Introduction. Continued fractions offer a useful means of expressing numbers and

functions. In the early ages, 300 b.c.200 a.d., mathematicians used other algorithms
and methods to express numbers and to express solutions of Diophantine equations.
Many of these algorithms were studied and modeled in the development of the continued
fractions. Through the eighteenth century, use of continued fractions was limited to the
area of mathematics.
Since the beginning of the twentieth century, continued fractions have become more
common in various other areas. For example, Robert M. Corless’s 1992 paper [3] exam-
ines the connection between chaos theory and continued fractions. They have also been
used in computer algorithms for computing rational approximations to real numbers,
as well as for solving Diophantine and Pell’s equations. This paper provides an intro-
duction to continued fractions. In Section 2, we discuss the general form of a continued
fraction. We also give some definitions and notations that are needed in later sections.
In Section 3, we trace the development of continued fractions over the past 2,500 years.
In Section 4, we begin looking at the theory of continued fractions. In particular, we
are going to see how to express real numbers as continued fractions. In Section 5, we
continue our look at the theory. We are going to see how to express rational numbers as
continued fractions. We note some similarities between this process and the Euclidean
algorithm. In Section 6, we discuss the kth convergent of a continued fraction. Finally,
in Section 7, we look at some applications. We are going to see how continued fractions
can be used to find solutions of quadratic equations, to express irrational numbers, and
to find factors of large numbers.

2. General Form. A continued fraction is an expression of the form

b1
r =0 +
b2
a1 +
b3
a2 +
a3 + . . .
where ai and bi are either rational numbers, real numbers, or complex numbers. If bi = 1
for all i, then the expression is called a simple continued fraction. If the expression
contains finitely many terms, then it is called a nite continued fraction; otherwise, it is
called an in nite continued fraction. The numbers ai are called the partial quotients .

11
12 MIT Undergraduate Journal of Mathematics

If the expression is truncated after k partial quotients, then the value of the resulting
expression is called the kth convergent of the continued fraction; it is denoted by Ck .
If the ai and bi repeat cyclically, then the expression is called a periodic continued
fraction. Due to the complexity of the expression above, mathematicians have adopted
several more convenient notations for simple continued fractions. The most common of
these is
r = [a0 , a1 , a2 , a3 , . . . ] .
If a0 is an integer, then it is often separated from the rest of the coefficients with a
semicolon:

r = [a0 ; a1 , a2 , a3 , . . . ]. (2-1)

Below, two other simpler notations are listed:

1 1 1
r = a1 + + + + ...; (2-2)
a2 + a3 + a4 +
r = a1 + 1(a2 + 1/(a3 + 1/(. . . )). (2-3)

In the remainder of this paper, we will use these simpler notations when possible.

3. Development. Early traces of continued fractions appear as far back as 306 b.c.
Other records have been found that show that the Indian mathematician Aryabhata
(475550) used a continued fraction to solve a linear equation [5, pp. 2832]. However,
he did not develop a general method; rather, he used continued fractions only in specific
examples. Continued fractions were used only in specific examples for more than 1,000
years. In the sixteenth century, two Italian mathematicians,
√ √ Rafael Bombelli (1526
72) and Pietro Cataldi (1548626), expressed 13 and 18, respectively, as periodic
continued fractions. Both mathematicians only provided these examples; they stopped
short of further investigation. John Wallis (1616703) did go further, and through his
work, continued fractions became a subject of study in its own right. First, in his 1656
book Arithemetica In nitorium, he worked out the formula,
4 3 × 3 × 5 × 5 × 7 × 7 × 9 × ...
= .
π 2 × 4 × 4 × 6 × 6 × 8 × 9 × ...
Although the right-hand side is not a continued fraction, Lord Brouncker (162084)
rewrote it as follows:
4 12 32 72
=1+ + + + ... .
π 2+ 2+ 2+
Brouncker did not go further with continued fractions. On the other hand, Wallis then
took the first steps toward a general theory.
In his 1695 book, Opera Mathematica, Wallis explained how to compute conver-
gents, and discovered some of their important properties. He also introduced the term
continued fraction.
Earlier, they were known as anthyphairetic ratios.
The Dutch
mathematician and astronomer, Christiaan Huygens (162995), made the first practical
application of the theory in 1687. He wrote a paper explaining how to use convergents
to find the best rational approximations for gear ratios. These approximations enabled
him to pick the gears with the best numbers of teeth. His work was motivated by his
desire to build a mechanical planetarium. Wallis and Huygens wrote the first general
Continued Fractions 13

works on continued fractions. Later, the theory grew when Leonard Euler (170783),
Johan Lambert (172877), and Joseph Louis Lagrange (17361813) worked on the topic.
Much of the modern theory was developed in Euler’s 1737 work, De Fractionbous
Continuis . He showed that every rational number can be expressed as a finite simple
continued fraction. He also gave the following expression for e as a continued fraction:
1 1 1 1 1 1 1 1 1
e−1=1+ + + + + + + + + + ... .
1+ 1+ 2+ 1+ 1+ 4+ 1+ 1+ 6+
He used this expression to show that e and e2 are irrational. He also showed how to go
from a series to a continued fraction, and back. In 1763, Lambert generalized Euler’s
work on e to show that both ex and tan x are irrational if x is rational. Lagrange
used continued fractions to find the value of an irrational root of a quadratic equation.
He also proved that a real irrational root is given by a periodic continued fraction.
The nineteenth century can be said to be a popular period for continued fractions,

according to Claude Brezinski [1, p. 12]. It was a time in which the subject was known
to every mathematician.
As a result, there was explosive growth, especially in the
part concerning convergents (see Theorem 6-1 and Theorem 6-2 below). Also studied
were continued fractions with complex numbers as terms. Among those to contribute
were Karl Jacobi (180451), Oskar Perron (18801975), Charles Hermite (18221901),
Karl Friedrich Gauss (17771855), Augustin Cauchy (17891857), and Thomas Stieltjes
(185694), see [2, pp. 12528]. By the beginning of the twentieth century, the theory
had advanced greatly beyond the initial work of Wallis.

4. Expression of Real Numbers. Every real number x is represented by a point on

the real line, and falls between two successive integers, say n and n + 1:
n ≤ x < n + 1.
In the case where x is an integer, then n = x. The integer n is often called the oor of
x, and is written as
n = bxc .
The number u = x − n satisfies 0 ≤ u < 1. Thus, for a given real x there is a unique
decomposition,
x = n + u,
where n is an integer and u satisfies 0 ≤ u < 1. Furthermore, u = 0 if and only if x is
an integer. This decomposition is called the mod one decomposition of a real number.
It is the first step in the process of expanding x as a continued fraction. The process of
finding the continued fraction expansion of a real number is a recursive process. Given
x, we begin with the mod one decomposition
x = n 1 + u1 , (4-1)
where n1 is an integer and 0 ≤ u < 1.
If u1 = 0, then the recursive process terminates with this first step. If u1 > 0, then
the reciprocal 1/u1 of u1 satisfies 1/u1 > 1 since u1 satisfies 0 ≤ u < 1. In this case,
the second step of the recursion is to apply the mod one decomposition to 1/u1 , which
yields
1/u1 = n2 + u2 , (4-2)
14 MIT Undergraduate Journal of Mathematics

where n2 is an integer and u2 satisfies 0 ≤ u2 < 1. Combining (4-1) and (4-2), we see
that
1
x = n1 + .
n 2 + u2
In general, if uk = 0, then the recursive process ends with
1
x = nk−1 + .
nk
In the case that uk > 0, we can rewrite 1/uk as

1/uk = nk+1 + uk+1 ,

where nk+1 is an integer uk+1 and satisfies 0 ≤ uk+1 < 1. After k steps, we can write
the real number as
1
x = n1 + .
1
n2 +
1
n3 +
1
··· +
n k + uk
We can express any real number as a continued fraction using the above recursive
process.

5. Expression of Rational Numbers. The process of expressing a rational number

as a continued fraction is essentially identical to the process of applying the Euclidean
algorithm to the pair of integers given by its numerator and denominator in lowest
terms. Let x = a/b, with b > 0, be a representation of a rational number x. The mod
one decomposition,
a a − n1 b
= n1 + u1 , where u1 = ,
b b
shows that u1 = r1 /b, where r1 is the remainder on division of a by b. The case where
u1 = 0 is the case where x is an integer. Otherwise u1 and the mod one decomposition
of 1/u1 gives
b b − n2 r1
= n2 + u2 , where u2 = .
r1 r1
Hence u2 = r2 /r1 where r2 is the remainder on division of b by r1 . The successive
quotients in the Euclidean algorithm are the integers n1 , n2 , . . . occurring in the con-
tinued fraction. The Euclidean algorithm terminates after a finite number of steps with
the appearance of a zero remainder. Therefore, the continued fraction of every rational
number is finite. We can now prove the following theorem.
Theorem 5-1. The continued fraction expression of a real number is nite if
and only if the real number is rational.
Proof: We have just shown that, if x is rational, then the continued fraction ex-
pansion of x is finite. To show the converse, we prove by induction that, if a simple
continued fraction has n terms, then it is rational. Let X represent the value of the
continued fraction. We first check the base case of n = 1. Then

X = a1 .
Continued Fractions 15

Since a1 is an integer, X is rational. Thus, the base case is true. We now prove the
inductive case. We assume that the statement is true for all i ≤ k, and show that the
statement is true for k + 1. Let X be a continued fraction that is represented by n + 1
terms. We want to show that X is rational. So, we have

X = [a1 ; a2 , a3 , . . . , an , an+1 ] .

We can rewrite this expression as

1
X = a1 + ,
Y
where Y = [a2 ; a3 , . . . , an , an+1 ]. The continued fraction X now has n terms, and by
hypothesis it can be written as follows:
1
X = a1 + p .
q

By doing some algebra, we see that

pa1 + q
X= .
p
Since a1 , p, and q are integers, X must be a rational. Therefore, the theorem is true for
n + 1, and so by induction, it must hold for all integers. The proof is now complete.
Corollary 5-2. If a real number is irrational, then its continued fraction ex-
pression is in nite.
Corollary 5-2 follows directly from Theorem 5-1.

6. Convergents. Below are two theorems involving the convergents of a continued

fraction.
Theorem 6-1. Given a continued fraction [a1 ; a2 , a3 , . . . , an−1 , an ], a numerator
pi and a denominator qi of the ith convergent Ci are given for all i ≥ 0 by the
recursive formulas,
pi = ai pi−1 + pi−2 ,
qi = ai qi−1 + qi−2 ,
where p−1 = 0, p0 = 1, q−1 = 1, and q0 = 1.
Proof: We prove this assertion by using induction. We first check the two base
cases:
p1 a1 a1 · 1 + 0
C1 = = a1 = = ;
q1 1 a1 · 0 + 1
p2 q1 q2 + 1 a 2 p1 + p0
C2 = = = .
q2 q2 a2 q 1 + q 0
Thus both base cases are true. We now assume that the assertion is true for all i ≤ k,
and show that it is true for k + 1. By the recursive formula,
pk+1
Ck+1 = = [a1 , a2 , . . . , ak , ak+1 ] .
qk+1
16 MIT Undergraduate Journal of Mathematics

We rewrite this fraction as follows:

pk+1
Ck+1 = = [a1 , a2 , a3 , . . . , ak , a0k+1 ]
qk+1

where a0k+1 = ak + 1/ak+1 . The continued fraction now has k terms, and by hypothesis,

a0k+1 pk−1 + pk−2

Ck+1 =
a0k+1 qk−1 + qk−2
(ak a0k+1 + 1)pk−1 + a0k+1 pk−2
=
(ak a0k+1 + 1)qk−1 + a0k+1 qk−2
ak a0k+1 + pk−1 + pk−1 + a0k+1 pk−2
=
ak a0k+1 + qk−1 + qk−1 + a0k+1 qk−2
a0k+1 (ak pk−1 + pk−2 ) + pk−1
=
a0k+1 (ak qk−1 + qk−2 ) + qk−1
a0k+1 pk + pk−1
= .
a0k+1 qk + qk−1

The last step used the induction hypothesis for the substitution. Thus, the theorem is
true for k + 1, and by induction, must hold for all integers. The proof is now complete.
Theorem 6-2 (Fundamental Recurrence Relation). Let pi and qi be the conver-
gents. Then
pi qi−1 − pi−1 qk = (−1)i for all i ≥ 0.
Proof: We will prove this statement by using induction. We first check the two base
cases, i = 1 and i = 2:

p0 q−1 − p−1 q0 = 1(1) − 0(0) = 1 = (−1)0 ;

p1 q0 − p0 q1 = (a1 p0 + p−1 )(0) − 1(a1 q0 + q1 )
= 0 − 1(0 + 1)
= −1
= −(1)1 .

Both cases are true. We now assume that the statement is true for all i ≤ k, and show
that the statement is true for k + 1:

pk+1 qk − pk qk+1 = (ak+1 pk + pk−1 )qk − pk (ak+1 qk + qk−1 )

= ak+1 pk qk + pk−1 qk − ak+1 pk qk − pk qk−1
= pk−1 qk − pk qk−1
= −(pk qk−1 − pk−1 qk )
= −(−1)k
= (−1)k+1 .

Since the assertion is true for k + 1, the assertion is true for all integers, by induction.
The proof is now complete.
Continued Fractions 17

7. Applications. In this section we consider some examples of the applications of con-

tinued fractions in mathematics. Several common methods are used to solve quadratic
equations, including the quadratic formula, normal
factoring, and graphing the equa-
tion. A less common method involves continued fractions, see [6, pp. 3237]. This
method is used less often because it requires more calculations, and in many cases it
reveals only one of the two solutions. For example, consider the quadratic equation,
x2 − 5x + 6 = 0. Factoring the left-hand side, we find the roots are 2 and 3.
We now use continued fractions. We begin by solving
x2 − 5x + 6 = 0 for x:

6
x=5− . (7-1)
x
Next, we express x as an infinite continued fraction. To do so we substitute the expres-
sion 5 − x6 in for x:

6 6
x=5− + . (7-2)
5− x
6
We repeat the substitution again, putting 5 − x into (7-2) and getting

6 6 6
x=5− + + . (7-3)
5− 5− x
Continuing this process, we produce an infinite continued fraction. Finally, we approx-
imate one of the roots. When we set x = 1 in the right-hand side of (7-1), we get −1.
Taking this value and plugging it into (7-2), we see that x = 11. Placing 11 in (7-3),
we see the result is x = 4.4545. If we continue this process, then we produce an infinite
sequence that approaches 3. If we change the initial value, then we produce a different
infinite sequence that approaches 3. Therefore one solution of this equation is x = 3,
and there is no way we can compute the second solution x = 2 using this method. The
method can be generalized and applied to solve any quadratic equation.
Some Diophantine equations can be solved using continued fractions, including Pell’s
equation, linear Diophantine equations, and congruence equations [7, pp. 12027]:

x2 − P y 2 = 1;
ax + by = c;
ax = b (mod m).

Section 5 explained a method used to express a rational number as a continued fraction.

Using continued fractions also provides a way to express an irrational number and to
approximate its value. This expression allows us to study certain interesting
√ properties
of an irrational number. For example, consider the irrational number 2. At first
glance, it may seem difficult to express this number as a continued fraction since its
decimal representation never ends. However, using steps similar to√the ones taken to
express a rational number as a continued fraction, we can express 2 as one also. √In
general, any irrational number can be expressed
√ as a continued fraction. To express 2
as a continued fraction, we observe that 2 > 1,
√
2 = 1 + 1/x. (7-4)
18 MIT Undergraduate Journal of Mathematics

Solving for some real number x, we find that

√
x = 1/( 2 − 1) .

To get rid of the

√ square root in the denominator, we multiply the numerator and de-
nominator by ( 2 + 1), obtaining
√
x = ( 2 + 1) .

Using (7-4) and simplifying, we obtain the equation,

x = 2 + 1/x.

This equation now looks like equation (7-1), which we obtained from the quadratic
equation, x2 − 5x + 6 = 0. Continuing as in Section 5, we obtain the continued fraction
representation of √
2 = [1; 2, 2, 2, 2, 2, 2, . . . ].
Other square roots and irrational numbers can be expressed similarly as a continued
fraction. In 1975, M.A. Morrison and J. Brillhart developed the Continued Fraction
Factorization Algorithm, which is a prime√ factorization algorithm that uses residues
produced by the continued fraction of mN . Here N is the number to be factored
and m is chosen as small as possible so that mN is a square. The algorithm solves the
equation x2 = y 2 ( mod N ) by finding an m for which m2 ( mod
√
N ) has the smallest pos-
sible value. This method has a theoretical runtime of O(e 2 log N log log N ), and was the
fastest prime factorization algorithm in use until the development of the quadratic sieve
method. This method
√ was developed in 1981 by Carl Pomerance and has a theoretical
runtime of O(e log N log log N ) .

References
[1] Beskin, N.M., Fascinating Fractions,
Mir Publishers, Moscow, 1980 (Translated
by V.I. Kisln, 1986).
[2] Brezinski, Claude, History of Continued Fractions and Pade Approximants,

Springer-Verlag, 1980.
[3] Corless, Robert, Continued Fractions and Chaos,
Amer. Math. Monthly, 1992.
[4] Hardy, G. and Wright, E., An Introduction to the Theory of Numbers,
Oxford
University Press, 1965.
[5] Kline, Morris, Mathematical Thought from Ancient to Modern Times,
Oxford
University Press, 1972.
[6] Moore, Charles D., An Introduction to Continued Fractions,
The National Council
of Teachers of Mathematics, Washington, D.C., 1964.
[7] Olds, C.D., Continued Fractions,
Random House, 1963.