Contents

1 Expansion of Rational Fractions 1

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Definitions and Notation . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Expansion of Rational Fractions . . . . . . . . . . . . . . . . . . . . . 4

1.4 Expansion of Rational Fractions

(General Discussion) . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 Convergents and Their Properties . . . . . . . . . . . . . . . . . . . . . 10

1.6 Some Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Diophantine Equations 18

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2 The Method Used Extensively by Euler . . . . . . . . . . . . . . . . . 19

2.3 The Indeterminate Equation ax − by = ±1 . . . . . . . . . . . . . . . 23

2.4 General Solution of ax − by = c, gcd(a, b) = 1 . . . . . . . . . . . . . 27

1
 2.5 General Solution of ax + by = c, gcd(a, b) = 1 . . . . . . . . . . . . . 28

2.6 The General Solution of Ax ± By = ±C . . . . . . . . . . . . . . . . 29

2.7 Sailors, Coconuts, and Monkeys . . . . . . . . . . . . . . . . . . . . . 30

3 Expansion of Irrational Numbers 33

3.1 Preliminary Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.2 Convergents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Chapter 1

Expansion of Rational Fractions

1.1 Introduction

Let’s solve a quadratic equation x2 − 3x − 1 = 0. The positive solution of this equation

can be find out as
p √
3+ 32 − 4 × 1 × (−1) 3 + 13 6.6055 . . .
x= = = = 3.30277
2 2 2
Or by some other method we can divide through by x and can write the equation in the
form
1
x=3+ .
x
The unknown quantity x is still found on the right-hand side of this equation and hence
can be replaced by its equal, namely 3 + x1 . This gives

1 1
x=3+ =3+ .
x 1
3+
x

1
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 2

1
Repeating this replacement of x by 3 + x
several more times we obtain the expression

1
x=3+ . (1.1)
1
3+
1
3+
1
3+
1
3+
x
Since x continues to appear on the right-hand side of this “multiple decked” fraction,
we do not seem to be getting any closer approximation to the solution of our quadratic
equation.
But let us look more closely at the right side of equation (1.1). We see that it contains a
succession of fractions,
1 1 1
3, 3+ , 3+ , 3+ ,..., (1.2)
3 1 1
3+ 3+
3 1
3+
3
obtained by stopping at consecutive [Link] numbers, when converted into frac-
tions and then into decimals, give in turn
10 33 109
3, = 3.333 . . . , = 3.3, = 3.30303 . . .
3 10 33
This gives a better approximation to the positive root of the quadratic equation, i.e., 3.302775 . . .
If we calculate more and more successive fractions (1.2), we can get better and better
√
approximation to x = 12 (3 + 13.) Also we can continue these fractions infinitely, non
terminating like
1
x=3+
1
3+
3 + ..
..
These multiple decked fractions are called Continued Fractions.
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 3

1.2 Definitions and Notation

An expression of the form

b1
a1 +
b2
a2 +
b3
a3 +
a4 + . .
..
is called a continued fraction. In general, the numbers a1 , a2 , a3 , . . . , b1 , b2 , b3 , . . . may
be any real or complex numbers, and the number of terms may be finite or infinite.
In this monograph however, we shall restrict our discussion to simple continued frac-
tions. These have the form
1
a1 + ,
1
a2 +
1
a3 +
a4 + . .
..
where the first term a1 is usually a positive or negative integer (but could be zero), and
where the terms a2 , a3 , a4 , . . . are positive integers.
Fractions of the form
1
a1 + ,
1
a2 +
1
a3 +
a4 + . . 1
. .+
1
an−1 +
an
are called finite simple continued fractions. A much more convenient way of writing
this is by the symbol [a1 , a2 , a3 , . . . , an ], so that
1
[a1 , a2 , a3 , a4 , . . . , an ] = a1 + .
1
a2 +
1
a3 +
a4 + . . 1
. .+
1
an−1 +
an
The terms a1 , a2 , . . . , an are called the partial quotients of the continued fraction.
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 4

1.3 Expansion of Rational Fractions

p
A rational number is a fraction of the form q
where p and q are integers with q 6= 0.
We shall see that every rational number can be expressed as a finite simple continued
fraction.
67
Example 1.3.1. The continued fraction for 29
is
67 1
=2+
29 1
3+
1
4+
2
or
67
= [2, 3, 4, 2]
29
To get this result first we divided 67 by 29 to obtain the quotient 2 and the remainder 9,
so that
67 9 1
=2+ =2+
29 29 29
9
9 29
Note that on the right we have replaced 29 by the reciprocal of 9
.
Next divide 29 by 9 to obtain
29 2 1
=3+ =3+ .
9 9 9
2
Finally, we divide 9 by 2 to obtain
9 1
=4+ ,
2 2
at which stage the process terminates. Now by combining all these expression
67 1 1 1
=2+ =2+ =2+
29 29 1 1
3+ 3+
9 9 1
4+
2 2
Or
67
= [2, 3, 4, 2] = [a1 , a2 , a3 , a4 ]
29
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 5

29
Example 1.3.2. Let us find the continued fraction expansion for 67
. We obtain

29 1
=0+
67 1
2+
1
3+
1
4+
2
To get this result,
29 1
=0+
67 67
29
67
And by substituting the continued fraction expansion of 29
in the above, we will have
29
the expansion for 67
.

A comparison of these two above expansions suggests that in a fraction pq ,if p is

greater than q and
p
= [a1 , a2 , . . . , an ]
q
then
q
= [0, a1 , a2 , . . . , an ]
p
If p is less than q and
q
= [a1 , a2 , . . . , an ]
p
then
p
= [0, a1 , a2 , . . . , an ]
q
67 67
But 29
= [2, 3, 4, 2] = [a1 , a2 , a3 , a4 ] is not only the expansion of 29
.This would be true
with a slight change in the last term, or last partial quotient, a4 . Since a4 = 2, we can
write
1 1 1
= =
a4 2 1
1+
1
Hence it is also true that
67
= [2, 3, 4, 1, 1]
29
Next, let us see the expansion of negative rational numbers.
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 6

−37
Example 1.3.3. To find the continued fraction expansion of 44
,
−37 7 1 1 1 1
= −1+ = −1+ = −1+ = −1+ = −1+ = [−1, 6, 3, 2]
44 44 44 2 1 1
6+ 6+ 6+
7 7 7 1
3+
2 2
1
or by replacing 12 with , we can get the continued fraction expansion of −37 =
1 44
1+
1
[−1, 6, 3, 1, 1] = [a1 , a2 , a3 , a4 , a5 ]. Here only a1 is negative.
134
Example 1.3.4. Continued fraction expansion of 58

134 1 1 1 1
=2+ =2+ =2+ =2+ = [2, 3, 4, 2]
58 58 4 1 1
3+ 3+ 3+
18 18 2 1
4+ 4+
4 2

134
The continued fraction expansion of 58
= 67×2
29×2
is same as the expansion of 67
29
.
In general, continued fraction expansion of ap
aq
is equal to the continued fraction expan-
p
sion of q
. This also illustrates an interesting [Link] we calculate
1
[2, 3, 4, 2] = 2 +
1
3+
1
4+
2
67 134 p
we would get back to 29
not to 58
. We always obtain a rational fraction q
in its lowest
terms, i.e., a fraction for which p and q have no factors greater than 1 in common.

1.4 Expansion of Rational Fractions

(General Discussion)

Theorem 1.4.1. Any finite simple continued fraction represents a rational number. Con-
p
versely, any rational number q
can be represented as a finite simple continued fraction;
with the exceptions, the expansion is unique.
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 7

Proof. One way of the theorem is obvious from what we have explained in our worked
examples, for if any expansion terminates we can always “back track” and build the
expansion into a rational fraction.
To prove the converse, let pq , q > 0, be any rational fraction. We divide p by q to obtain

p r1
= a1 + , 0 ≤ r1 < q,
q q

where a1 is the unique integer so chosen as to make the remainder r1 greater than or
equal to 0 and less than q. As we saw in the worked examples, a1 can be negative, zero,
p
or positive. If r1 = 0, the process terminates and the continued fraction expansion for q

is [a1 ].
If r1 6= 0, we write
p 1
= a1 + q , 0 < r1 < q,
q
r1
and repeat the division process, dividing q by r1 to obtain

q r2
= a2 + 0 ≤ r2 < r1 .
r1 r1
q
Notice now that r1
is a positive fraction, so a2 is the unique largest positive integer that
makes the remainder r2 a number between 0 and r1 . If r2 = 0, the process stops and we
q
substitute r1
= a2 to obtain

p 1
= a1 + = [a1 , a2 ]
q a2

as the continued fraction expansion for pq .

If r2 6= 0, we write
q 1
= a2 + r1 , 0 < r2 < r1
r1
r2
r1
and repeat the division process using . We observe that the calculations stop when we
r2
come to a remainder rn = 0.
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 8

It is possible to arrive at an rn , which is zero, so that the division process continues in-
definitely. For the remainders r1 , r2 , r3 , . . . form a decreasing sequence of non-negative
integers q > r1 > r2 > r3 > . . . and unless we come eventually to a remainder rn
which is equal to zero, we shall be in the ridiculous position of having discovered an
infinite number of distinct positive integers all less than a finite positive integer q.
Hence, by successive divisions we obtain a sequence of equation
p r1
= a1 + , 0 < r1 < q,
q q
q r2
= a2 + , 0 < r2 < r1 ,
r1 r1
r1 r3
= a3 + , 0 < r3 < r2 ,
r2 r2 (1.3)
......... ......
rn−3 rn−1
= an−1 + , 0 < rn−1 < r−2 ,
rn−2 rn−2
rn−2 0
= an + = an + 0, rn = 0,
rn−1 rn−1
terminating, after a certain finite number of divisions, with the equation in which the
remainder rn is equal to zero.
p
It is now easy to represent q
as a finite simple continued fraction. From the first two
equations in (1.3) we have

p 1 1
= a1 + q = a1 +
q 1
r1 a2 + r1
r2
r1
Using the third equation in (1.3) we replace r2
by

1
a3 + r2 ,
r3
and so on, until finally we obtain the expansion

p
= [a1 , a2 , a3 , . . . , an ]. (1.4)
q
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 9

The uniqueness of the expansion (1.4) follows from the manner in which the ai ’s are
calculated. This statement must be accompanied, however, by the remark that once the
expansion has been obtained we can always modify the last term an so that the number
of terms in the expansion is either even or odd, as we choose. To see this, notice that if
an is greater than 1 we can write

1 1
=
an 1
(an − 1 + )
1
so that (1.4) can be replaced by

p
= [a1 ,2 , . . . , an−1 , an − 1, 1].
q

On the other hand, if an = 1, then

1 1
= ,
1 (an−1 + 1)
an−1 +
an
so that (1.4) becomes
p
= [a1 , a2 , . . . , an−2 , an−1 + 1]
q


Hence we have the following theorem:

p
Theorem 1.4.2. Any rational number q
can be expressed as a finite simple continued
fraction in which the last term can be modified so as to make the number of terms in the
expansion either even or odd.

29
Example 1.4.1. Continued fraction expansion of 5

29 4 1 1
=5+ =5+ =5+ = [5, 1, 4]
5 5 5 1
1+
4 4
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 10

1 1
The last term can be replaced by
4 1
3+
1
29 1
Then =5+ = [5, 1, 3, 1]
5 1
1+
1
3+
1
−29
Example 1.4.2. Continued fraction expansion of 5

−29 1
= −6 + = [−6, 5]
5 5
or
−29 1 1
= −6 + = −6 + = [−6, 4, 1]
5 5 1
4+
1

1.5 Convergents and Their Properties

From the partial quotients of continued fractions, we can form the fractions
a1 1 1
c1 = , c2 = a1 + , c3 = a1 + ,...
1 a2 1
a2 +
a3
They are obtained in succession, by cutting off the expansion process after the first,
second, third,... steps. These fractions are called first, second, third,... convergents of
the continued fractions respectively.
Where nth convergent is giben by
1
c n = a1 +
1
a2 +
1
a3 +
a4 + . . 1
. .+
1
an−1 +
an
And this is equal to the finite continued fraction itself.
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 11

To compute these convergents, we write

p1
c1 =a1 = ,
q1
p1 = a1 , q1 = 1
1 a1 a2 + 1 p2
c2 =a1 + = = ,
a2 a2 q2
p2 = a1 a2 + 1, q2 = a2
1 a3 a1 a2 a3 + a1 + a3
c3 =a1 + = a1 + =
1 a2 a3 + 1 a2 a3 + 1
a2 +
a3
a3 (a1 a2 + 1) + a1 a3 p2 + p1 p3
= = = ,
a3 a2 + 1 a3 q 2 + q 1 q3
p3 = a3 p2 + p1 , q3 = a3 q2 + q1
1 1 a3 a4 + 1
c4 =a1 + = a1 + a = a 1 +
1 a2 +
4 a2 a3 a4 + a2 + a4
a2 + a3 a4 + 1
1
a3 +
a4
a1 a2 a3 a4 + a1 a2 + a1 a4 + a3 a4 + 1
=
a2 a3 a4 + a2 + a4
a4 (a1 a2 a3 + a1 + a3 ) + a1 a2 + 1 a4 p 3 + p 3 p4
= = = ,
a4 (a2 a3 + 1) + a2 a4 q 3 + q 2 q4
p4 = a4 p3 + p2 , q4 = a4 q3 + q2
pi
In general ci = [a1 , a2 , . . . , ai ] = qi
and

pi = ai pi−1 + pi−2 and qi = ai qi−1 + qi−2 for i = 3, 4, 5, . . . , n

Theorem 1.5.1. The numerators pi and the denominators qi of the ith convergent ci of
the continued fraction [a1 , a2 , . . . , an ] satisfy the equations

pi = ai pi−1 + pi−2 and qi = ai qi−1 + qi−2 for i = 3, 4, 5, . . . , n

with the initial values

p1 = a1 , p2 = a2 a1 + 1, q1 = 1, q2 = a2 .
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 12

Proof. We have to prove that ci = pqii is ith convergent of a continued fraction. c1 =

p1 a1 p2 a2 a1 + 1 1
= and c2 = = = a1 +
q1 1 q2 a2 a2
By induction, assume this is true for n − 1 i.e.,
pn−1 an−1 pn−2 + pn−3
cn−1 = = (1.5)
qn−1 an−1 qn−2 + qn−3
Also
1
cn−1 = a1 +
1
a2 +
a3 + . . 1
. .+
1
an−2 +
an−1
and
1
c n = a1 +
1
a2 +
a3 + . . 1
. .+
1
an−1 +
an
1
We obtain cn from cn−1 by replacing the last term an−1 of cn−1 by an−1 + an
, while
1
leaving a1 , a2 , a3 , . . . , an−2 unaltered. Hence if we replace an−1 by an−1 + an
in (1.5),
we will obtain
1
(an−1 + )pn−2 + pn3
an
cn =
1
(an−1 + )qn−2 + qn−3
an
pn−2
pn−2 an−1 + + pn−3
an
= qn−2
qn−2 an−1 + + qn−3
an
pn−2
pn−1 +
an an pn−1 + pn−2
= qn−2 = a q
qn−1 + n n−1 + qn−2
an
pn
=
qn
Hence this is true for all n.
pi
∴ ci =
qi
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 13

with the initial values

p1 = a1 , p2 = a2 a1 + 1, q1 = 1, q2 = a2 .


120
Example 1.5.1. Convergents of 49
.
120
The continued fraction expansion of 49
is [2, 2, 4, 2, 2].
i.e., a1 = 2, a2 = 2, a3 = 4, a4 = 2, a5 = 2.
Then
p1 = a1 = 2, q1 = 1
p2 = a1 a2 + 1 = 2 × 2 + 1 = 5, q2 = a2 = 2
p3 = a3 p2 + p1 = 4 × 5 + 2 = 22, q3 = a3 q2 + q1 = 4 × 2 + 1 = 9
p4 = a4 p3 + p2 = 2 × 22 + 5 = 49, q4 = a4 q3 + q2 = 2 × 9 + 2 = 20
p5 = a5 p4 + p3 = 2 × 49 + 22 = 120, q5 = a5 q4 + q3 = 2 × 20 + 9 = 49.
Then the convergents are
c1 = 2, c2 = 25 , c3 = 22
9
, c4 = 49
20
, c5 = 120
49

pn
Theorem 1.5.2. The convergent cn = qn
satisfy the relation

pn qn−1 − pn−1 qn = (−1)n for n = 2, 3, 4, . . .

Proof.

pn qn−1 − pn−1 qn = (an pn−1 + pn−2 )qn−2 − pn−1 (an qn−1 + qn−2 )

− (pn−1 qn−2 − pn−2 qn−1 )

we can write tn = −tn−1 where tn = pn qn−1 − pn−1 qn

−tn−1 = −pn−1 qn−2 + pn−2 qn−1

= −(an−1 pn−2 + pn−3 )qn−2 + pn−2 (an−1 qn−2 + qn−3 )

= −an−1 pn−2 qn−2 − pn−3 qn−2 + pn−2 qn−1 qn−2 + pn−2 qn−3

= pn−2 qn−3 − pn−3 qn−2 = tn−2

CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 14

Then
tn = (−1)1 tn−1 = (−1)2 tn−2 = · · · = (−1)n−2 t2

t2 = p2 q1 − p1 q2 = (a1 a2 + 1) − a1 a2 = 1

⇒ tn = (−1)n−2 t2 = (−1)n−2 = (−1)n

∴ pn qn−1 − pn−1 qn = (−1)n for n = 2, 3, 4, . . .

Example 1.5.2. A problem from BHASKARA(II)-Lilavati.

Solve in positive integers.
100x + 90
=y
63
or
100x − 63y = −90

100
The continued fraction expansion for 63
is

100
= [1, 1, 1, 2, 2, 1, 3]
63
i.e., a1 = 1, a2 = 1, a3 = 1, a4 = 2, a5 = 2, a6 = 1, a7 = 3.
Then
p1 = a1 = 1, q1 = 1
p2 = a1 a2 + 1 = 2, q2 = a2 = 1
p3 = a3 p2 + p1 = 3, q3 = a3 q2 + q1 = 2
p4 = a4 p3 + p2 = 8, q4 = a4 q3 + q2 = 5
p5 = a5 p4 + p3 = 19, q5 = a5 q4 + q3 = 12
p6 = a6 p5 + p4 = 27, q6 = a6 q5 + q4 = 17
p7 = a7 p6 + p5 = 100, q7 = a7 q6 + q5 = 63.
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 15

By 1.5.2, pn qn−1 − pn−1 qn = (−1)n

Since here n = 7,
pn = p7 = 100, qn = q7 = 63, pn−1 = p6 = 27, and qn−1 = q6 = 17

100 × 17 − 63 × 27 = (−1)7 = −1

If (qn−1 , pn−1 ) = (x0 .y0 ), then

100x0 − 63y0 = −1

Multiplying throughout the equation by 90,

100x1 − 63y1 = −90

where x1 = 90x0 = 90 × 17 = 1530 and y1 = 90y0 = 90 × 27 = 2430.

Therefore (x1 , y1 ) = (1530, 2430) is its one solution.
To get all the solutions, equate 100x − 63y = −90 and 100x1 − 63y1 = −90.
Then
100x − 100x1 = 63y − 63y1
x − x1 y − y1
= = t, t ∈ Z
63 100
x = 63t + x1 = 1530 + 63t and y = 100t + y1 = 2430 + 100t, t∈Z

pi
Corollary 1.5.1. Every convergent ci = qi
, i > 1 of a simple continued fraction is in
its lowest terms. i.e., gcd(pi , qi ) = 1.

Proof. By 1.5.2, pi qi−1 − pi−1 qi = (−1)i , i > 1 Since this equation is a linear combi-
nation of pi and qi , any number which divides both of them must divide (−1)i . But the
only divisor of (−1)i is 1 and −1.i.e., ±1 are the only common divisors of pi and qi .
∴ gcd(pi , qi ) = 1. 
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 16

1.6 Some Historical Notes

The earliest traces of the idea of a continued fraction are somewhat confused, for many
ancient arithmetical results are suggestive of these fractions, but there was no systematic
development of the subject.
Euclid’s method for finding the gcd of two numbers is essentially that of converting
a fraction into a continued fraction. This is perhaps the earliest (300 B.c.) important
step in the development of the concept of a continued fraction. A reference to continued
fractions is found in the works of the Indian mathematician Aryabhata, who died around
550 A.D. His work contains one of the earliest attempts at the general solution of a linear
indeterminate equation by the use of continued fractions. Further traces of the general
concept of a continued fraction are found occasionally in Arab and Greek writings. Most
authorities agree that the modern theory of continued fractions began with the writings
of Rafael Bombelli, a native of Bologna. His treatise on algebra (1572) contains a
chapter on square roots. In our modern symbolism he showed, for example, that

√ √ √ 4
13 = 9+4= 32 + 4 = 3 +
4
6+
6 + ..
..
This indicates that
√ b
a2 + b = a +
b
2a +
2a + . .
..
The next writer to consider these fractions was Pietro Antonio Cataldi (1548-1626), also
√
a native of Bologna. In a treatise on the theory of roots (1613), he expressed 18 in the
form
2 2 2
4& & & . . .
8 8 8
which is substantially the modern form
CHAPTER 1. EXPANSION OF RATIONAL FRACTIONS 17

√ √ √ 2
18 = 16 + 2 = 42 + 2 = 4 +
2
8+
8 + ..
..
A third early writer who deserves mention is Daniel Schwenter (1585-1636), who was
at various times professor of Hebrew, Oriental languages, and mathematics at the Uni-
versity of Altdorf, Germany. In his book Geometrica Practica he found approximations
177
to by finding the gcd of 177 and 233, and from these calculations he determined the
233
79 177
convergents 104 , 19 , 3, 1, 0.
25 4 1 1
= [0, 1, 3, 6, 4, 2] and
233
c1 = 0,
1
c2 = 0 + 1
=1
13
c3 = 0 + 1 =4
1+
3
1 19
c4 = 0 + =
1 25
1+
1
3+
6
1 79
c5 = 0 + = .
1 104
1+
1
3+
1
6+
4
In the discussion of Brouncker’s fraction in his book Arithmetica Injinitorum, published
in 1655, Wallis stated a good many of the elementary properties of the convergents to
general continued fractions, including the rule for their formation. He also used for the
first time the name “continued fraction”.
Continued fractions play an important role in present day mathematics. They constitute
a most important tool for new discoveries in the theory of numbers and in the field of
Diophantine approximations.
Chapter 2

Diophantine Equations

2.1 Introduction

A great many puzzles, riddles, and trick questions lead to mathematical equations whose
solutions must be integers. Consider a problem: : A farmer bought a number of cows
at $80 each, and a number of pigs at $50 each. His bill was $810. How many cows and
how many pigs did he buy?
If x is the number of cows and y the number of pigs, we have the equation

80x + 50y = 810

which is equivalent to
8x + 5y = 81 (2.1)
1
If nothing limits the values of x and y in equation (2.1), we can give x any value, say 2
, and then solve the resulting equation

4 + 5y = 81
77
for y, getting y = 5
. In this sense, (2.1) is an indeterminate equation, which means that
we can always find some value of y corresponding to any value we choose for x.

18
CHAPTER 2. DIOPHANTINE EQUATIONS 19

If, however, we restrict the values of x and y to be integers, as the farmer is likely to
do (since he is probably not interested in half a cow), then our example belongs to an
extensive class of problems requiring that we search for integral solutions x and y of in-
determinate equations. Indeterminate equations to be solved in integers (and sometimes
in rational numbers) are often called Diophantine equations in honor of Diophantus, a
Greek mathematician of about the third century A.D., who wrote a book about such
equations. Our problem, it should be noted, has the further restriction that both x and y
must not only be integers but must be positive.
In fact there is no harm in solving such equations by trial and error or by making intel-
ligent guesses. For example, if we write equation (2.1) in the form

81 − 8x = 5y

we need only search for positive integral values of x such that 81 − 8x is a multiple of
5. Letting x, in turn, take on the values 0, 1, 2, 3, . . . , 10, we find that x = 2 and
x = 7 are the only non-negative values which make 81 − 8x a non-negative multiple of
5. Then y = 13 and y = 5 respectively.
Hence two solutions for this problem are (2, 13) and (7, 5).
There are other ways of solving Diophantine equations. The first of these was used
extensively by Euler in his popular text Algebra, published in 1770

2.2 The Method Used Extensively by Euler

Consider again the equation (2.1)

8x + 5y = 81

Since y has the smaller coefficient, we solve the equation for y, getting
81 − 8x
y=
5
Both 81 and 8 contain multiples of 5, that is
CHAPTER 2. DIOPHANTINE EQUATIONS 20

81 = 5 × 16 + 1 and 8=5×1+3

(5 × 16 + 1) − (5 × 1 + 3)x
y=
5
1 − 3x (2.2)
= 16 − x +
5
= 16 − x + t

where
1 − 3x
t=
5
or
5t + 3x = 1

Since x and y must be integers, we conclude from equation (2.2) that t must be an
integer. This is the essential idea in Euler’s method to show that integral solutions of
given equation are in turn connected with the integral solutions of similar equation with
the smaller coefficient.
Now solving the last equation by the above discussed procedure,

5t + 3x =1
1 − 5t
x=
3
1 − (2.3 − 1)t
= (2.3)
3
1+t
= − 2t +
3
= − 2t + u

where
1+t
u=
3
or
3u − t = 1

t = 3u − 1
CHAPTER 2. DIOPHANTINE EQUATIONS 21

Again, since x and t must be integers, u must also be an integer.

Now,

x = − 2t + u = −2(3u − 1) + u
= − 6u + u + 2 = 2 − 5u
and (2.4)
y =16 − x + t = 16 − (2 − 5u) + (3u − 1)
=16 − 2 + 5u + 3u − 1 = 8u + 13

∴ x = 2 − 5u and y = 13 + 8u, u∈Z

Substituting the values of x and y in equation (2.1),

8(2 − 5u) + 5(13 + 8u) = 81

16 − 40u + 65 + 10u = 81

which means this eqaution has infinite number of solutions, one for each integral
value of u. A few solutions are listed below

u -3 -2 -1 0 1 2 3
x 17 12 7 2 -3 -8 -13
y -11 -3 5 13 21 29 37

If the problem is such that we are limited to positive values of x and y, then two
inequalities must be solved,

x = 2 − 5u > 0 and y = 13 + 8u > 0

2 −13
=⇒ u < and u >
5 8
Then the only possible integral values of u are 0 and −1, which leads to the solutions
(x, y) = (2,13) and (7,5).

Example 2.2.1. Use Euler’s method to solve the linear Diophantine equations, 31x +
7y = 1. And list the positive integral solutions.
CHAPTER 2. DIOPHANTINE EQUATIONS 22

31x + 7y =1
1 − 31x
y=
7
1 − (4.7 + 3)x
=
7
1 − 3x
= − 4x
7
=t − 4x
where
1 − 3x
t=
7
or
7t + 3x = 1
Then
1 − 7t
x=
3
1 − (2.3 + 1)t
=
3
1−t
= − 2t
3
=u − 2t
where
1−t
u= , u∈Z
3

or
t = 1 − 3u

Now,
x = − 2t + u = −2(1 − 3u) + u
=6u + u − 2 = 7u − 2
and (2.5)
y =t − 4x = 1 − 3u − 4(7u − 2)
=1 − 3u − 28u + 8 = 9 − 31u
CHAPTER 2. DIOPHANTINE EQUATIONS 23

∴ x = 7u − 2 and y = 9 − 31u, u∈Z

Substituting the values of x and y in the above equation,

31(7u − 2) + 7(9 − 31u) = 1

217u − 62 + 63 − 217u = 1

which means this eqaution has infinite number of solutions, one for each integral value
of u. If the problem is such that we are limited to positive values of x and y, then two
inequalities must be solved,

x = 7u − 2 > 0 and y = 9 − 31u > 0

2 9
=⇒ u > = 0.28 and u < = 0.29
7 31
We cannot find integral value of u satisfying these two inequalities.
∴ There doesnot exist a positive integral value for x and y.

2.3 The Indeterminate Equation ax − by = ±1

Theorem 2.3.1. The equation ax − by = 1, where a and b are relatively prime positive
integers, has an infinite number of integral solutions (x, y).

a
Proof. We first convert b
into a finite simple continued fraction
a
= [a1 , a2 , . . . , an−1 , an ]
b
where ai ’s are the partial quotients of simple finite continued fraction ab . Let c1 , c2 , . . . , cn−1 , cn
are its convergents. Then
pn−1 pn a
cn−1 = and cn = =
qn−1 qn b
CHAPTER 2. DIOPHANTINE EQUATIONS 24

By theorem (1.5.2) we know

pn qn−1 − pn−1 qn = (−1)n

Since pn = a and qn = b, we have

aqn−1 − pn−1 b = (−1)n .

Case(i): n is even.
Then
aqn−1 − pn−1 b = 1

Comparing this with the given equation, ax − by = 1, we will get one solution

x0 = qn−1 , y0 = pn−1 ,

which is a particular solution.

Case(ii): n is odd.
a
We can rewrite b
= [a1 , a2 , . . . , an−1 , an ] as

[a1 , a2 , . . . , an−1 − 1, 1], if an > 1


[a1 , a2 , . . . , an−1 + 1],


if an = 1.
pn−1
In both cases the number of partial quotients is even. So now we can recalculate qn−1
pn
and qn
, so that again we will get aqn−1 − pn−1 b = 1, which will yield a particular
solution.
Now to find general solution,
let (x, y) be any other solution, then ax − by = 1 and ax0 − by0 = 1

a(x − x0 ) = b(y − y0 )

This shows that b divides the left side of the equation. But b cannot divide a since a
and b are relatively prime; hence b must divide (x − x0 ), that is, (x − x0 ) is an integral
multiple of b, and we may write

x − x0 = tb, t∈Z
CHAPTER 2. DIOPHANTINE EQUATIONS 25

or
x = x0 + tb, t∈Z

Then
a(tb) = b(y − y0 )

so that
y − y0 = ta

It follows that any other solution (x, y) of ax − by = 1 has the form

x =x0 + tb, t∈Z

(2.6)
y =y0 + ta, t∈Z

Conversely, if (x0 , y0 ) is any particular solution of ax − by = 1, and if we set up the

equations (2.8) with t any integer whatever, then the values (x, y) will satisfy the given
equation, because

ax − by =a(x0 + tb) − b(y0 + ta)

=(ax0 − by0 ) + tab − tab

=ax0 − by0 = 1

Thus (x, y) is the general solution of the indeterminate equation ax − by = 1.

Example 2.3.1. Find the integral solutions of 205x − 93y = 1

Since 205 and 93 are relatively prime, by theorem 2.3.1 this equation has solutions.
205
Continued fraction expansion of is [2, 4, 1, 8, 1, 1]
93
Here n = 6
CHAPTER 2. DIOPHANTINE EQUATIONS 26

i 1 2 3 4 5 6
ai 2 4 1 8 1 1
pi 2 9 11 97 108 205
qi 1 4 5 44 49 93

Then pn−1 = p5 = y0 = 108 and qn−1 = q5 = x0 = 49.

Then the particular solution of 205x − 93y = 1 is (x0 , y0 ) = (49, 108).
And general solution can be given by

x =49 + t93, t∈Z

(2.7)
y =108 + t205, t∈Z
Example 2.3.2. Find the integral solutions of 205x − 93y = −1

Since 205 and 93 are relatively prime, by theorem 2.3.1 this equation has solutions.
205
Continued fraction expansion of is [2, 4, 1, 8, 1, 1]
93
Since RHS of the equation is −1, we need odd number of partial quotient.
205
Then n = 5 and is [2, 4, 1, 8, 2]
93

i 1 2 3 4 5
ai 2 4 1 8 2
pi 2 9 11 97 205
qi 1 4 5 44 93

Then pn−1 = p4 = y0 = 97 and qn−1 = q4 = x0 = 44.

Then the particular solution of 205x − 93y = −1 is (x0 , y0 ) = (44, 97).
And general solution can be given by

x =44 + t93, t∈Z

(2.8)
y =97 + t205, t∈Z
CHAPTER 2. DIOPHANTINE EQUATIONS 27

2.4 General Solution of ax − by = c, gcd(a, b) = 1

We know to solve ax − by = ±1, (a, b) = 1. If (x0 , y0 ) is any particular solution, then

we have
ax0 − by0 = ±1

Then
a(cx0 ) − b(cy0 ) = ±c

∴ (cx0 , cy0 ) is the solution for ax − by = ±c.

Example 2.4.1. Solve the equation

205x − 93y = 5

From Example 2.3.1 we know that (x0 , y0 ) = (49, 108) is a particular solution of
the equation 205x − 93y = 1, the is,

205(49) − 93(108) = 1

Multiplying both sides by 5 we get,

205(5.49) − 93(5.108) = 5

So that (5x0 , 5y0 ) = (245, 540) is a particular solution of the given equation. Then the
general solution, according to 2.8 is given by

x =245 + t93, t∈Z

y =540 + t205, t∈Z
CHAPTER 2. DIOPHANTINE EQUATIONS 28

2.5 General Solution of ax + by = c, gcd(a, b) = 1

a
From the continued fraction expansion of , with an even number of partial quotients,
b
we can get pn−1 and qn−1 . Then

aqn−1 − bpn−1 = 1

Now we have to write the given equation ax + by = c in the form

ax + by = c.1 = c(aqn−1 − bpn−1 )

Rearrange terms to obtain

a(cqn−1 − x) = b(y + cpn−1 )

This shows that b divides the left side of the equation; but gcd(a, b) = 1, so b cannot
divide a. Therefore b divides cqn−1 − x, so that there is an integer t such that

cqn−1 − x = bt

or
x = cqn−1 − bt
Then
y = at − cpn−1

Example 2.5.1. Solve the indeterminate equation

13x + 17y = 300

Since 13 and 17 are relatively prime, this equation has solutions.

13
Continued fraction expansion of 17
= [0, 1, 3, 4] with n = 4

i 1 2 3 4
ai 0 1 3 4
pi 0 1 3 13
qi 1 1 4 9
CHAPTER 2. DIOPHANTINE EQUATIONS 29

Then pn−1 = p3 = y0 = 3 and qn−1 = q3 = x0 = 4.

We find that (x0 , y0 ) = (4, 3) is a particular solution of 13x − 17y = 1,

Then

13x + 17y = 300 = 300(13.4 − 17.3)

= 13.1200 − 17.900
13(x − 1200) = −17(900 + y)

⇒ x = 1200 − 17t and y = 13t − 900, t∈Z

2.6 The General Solution of Ax ± By = ±C

Not all equations of this form have solutions.

Let d = gcd(A, B)
If d doesnot divide C, then the equation doesnot have integral solutions and if d divides
C, then we can reduce this equation to ax + by = ±c, where gcd(a, b = 1) which have
solutions.

Example 2.6.1. Solve the equation

410x − 186y = 10

gcd(410, 186) = 2
Since d = 2 divides 10, the equation can be solved. Divide the given equation by 2 to
obtain
205x − 93y = 5

where now 205 and 93 are relatively prime. and then the general solution is

x =245 + t93, t∈Z

y =540 + t205, t∈Z
CHAPTER 2. DIOPHANTINE EQUATIONS 30

2.7 Sailors, Coconuts, and Monkeys

Five sailors were cast away on an island. To provide food, they collected all the coconuts
they could find. During the night one of the sailors awoke and decided to take his share
of the coconuts. He divided the nuts into five equal piles and discovered that one nut
was left over, so he threw this extra one to the monkeys. He then hid his share and went
back to sleep. A little later a second sailor awoke and had the same idea as the first. He
divided the remainder of the nuts into five equal piles, discovered also that one was left
over, and threw it to the monkeys. Then he hid his share.
In their turn the other three sailors did the same thing, each throwing a coconut to the
monkeys. The next morning the sailors, all looking as innocent as possible, divided the
remaining nuts into five equal piles, no nuts being left over this time. The problem is to
find the smallest number of nuts in the original pile. In order to solve this problem, let
x be the original number of coconuts. The first sailor took 15 (x − 1) coconuts and left
4
5
(x − 1).
To check this,
x − 1 4(x − 1)
1+ + =x
5 5
Similarly the second sailor took

1  4(x − 1)  4x − 9
−1 =
5 5 5
coconuts and left
4  4(x − 1)  16x − 36
−1 =
5 5 25
Number of coconuts the third sailor took is
1  16x − 36  16x − 61
−1 =
5 25 125
and left is
4  16x − 36  64x − 244
−1 =
5 25 125
Similarly coconuts left by the fourth sailor is
4  64x − 244  256x − 1476
−1 =
5 125 625
CHAPTER 2. DIOPHANTINE EQUATIONS 31

and coconuts left by the fifth sailor is

4  256x − 1476  1024x − 8404
−1 =
5 625 3125
Now the number of nuts in the last pile must be a multiple of 5 since it was divided
evenly into five piles with no nuts left over.
Hence
1024x − 8404
= 5y
3125
where y is some integer. Multiplying both sides by 3125 we obtain the indeterminate
equation
1024x − 15625y = 8404 (2.9)

Factoring into primes we find 1024 = 21 0 and 15625 = 56 ; hence these numbers are
relatively prime and the equation (2.9) has integral solutions.
First we can find the particular solution of this equation. For, consider

1024x − 15625y = 1
1024
The continued fraction expansion of is [0, 15, 3, 1, 6, 2, 1, 3, 2, 1].
15625
Here n = 10. The convergents of the continued fraction are calculated:

i 1 2 3 4 5 6 7 8 9 10
ai 0 15 3 1 6 2 1 3 2 1
pi 0 1 3 4 27 58 85 313 711 1024
qi 1 15 46 61 412 885 1297 4776 10849 15625
The convergent c9 yields the particular solution x0 = q9 = 10849, and y0 = p9 = 711
of equation 1024x − 15625y = 1.
. Hence xo = 8404x1 = 91174996, and yo = 8404y1 = 5975244 will be a particular
solution of equation (2.9). The general solution is

x =91174996 + t15625, t∈Z

y =5975244 + t1024, t∈Z
CHAPTER 2. DIOPHANTINE EQUATIONS 32

Since both x and y must be positive, we search for the value of t which gives the smallest
positive value of x and which at the same time makes y positive. From (2.7) we find
that t must be an integer satisfying the two inequalities

91174996
t>− = −5835.2 . . . ,
15625
5975244
t>− = −5835.1 . . .
1024
Hence the required value is t = −5835. Introducing this value of t into equations (2.7),
we finally obtain
x = 3121 and y = 204

which means that the original number of coconuts was 3121 and each sailor received
204 in the final distribution.
Chapter 3

Expansion of Irrational Numbers

So far we seen that a rational number can be expanded into a finite simple contin-
ued fraction and conversely, every finite simple continued fraction represents a rational
number.
An irrational number is one which cannot
√ be represented as the ratio of two integres.
√ √ √ 3+ 7
For example 2, − 3, 1 ± 2, ,...
√ 5
P± D
A number of the form , where P, D, Q are integers, and where D is a positive
Q
integer not a perfect square, is irrational. A number of this form is called a quadratic
irrational or quadratic surd since it is the root of the quadratic equation

Q2 x2 − 2P Qx + (P 2 − D) = 0

There are irrational numbers which are not quadratic surds. The irrational number
√
π = 3.14159 . . . is one example. The irrational number 2 is the solution of the alge-
braic equation x2 − 2 = 0, and is therefore called an ”algebraic number”. An algebraic
number is a number x which satisfies an algebraic equation, i.e., an equation of the form

a0 xn + a1 xn−1 + · · · + an = 0

where a0 , a1 , . . . are integers, not all zero. A number which is not algebraic is called a

33
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 34

transcendental number.

3.1 Preliminary Examples

Let x be the given irrational number. Calculate a1 , the greatest integer less than x, and
express x in the form
1 1
x = x 1 = a1 + , 0< <1
x2 x2
where the number
1
x2 = >1
x − a1
is irrational; for, if an integer is subtracted from an irrational number, the result and the
reciprocal of the result are irrational. To continue, calculate a2 , the largest integer less
than x2 , and express x2 in the form
1 1
x 2 = a2 + , 0< < 1, a2 ≥ 1
x3 x3
where, again, the number
1
x3 = >1
x 2 − a2
is irrational.
This calculation may be repeated indefinitely, producing in succession the equations
1
x = a1 + , x2 > 1
x2
1
x 2 = a2 + , x3 > 1, a2 ≥ 1
x3
1
x 3 = a3 + , x4 > 1, a3 ≥ 1
x4 (3.1)
...... ... ...
1
x n = an + , xn+1 > 1, an ≥ 1
xn+1
...... ... ...

where a1 , a2 , . . . an , . . . , are all integers and where the numbers x, x2 , x3 , x4 , . . . are all
irrational. This process cannot terminate, for the only way this could happen would be
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 35

for some integer an to be equal to xn , which is impossible since each successive xi , is

irrational.

Substituting x2 from the second equation in (3.1) into the first equation, then x3
from the third into this result, and so on, produces the required infinite simple continued
fraction.
1 1 1
x = a1 + = a1 + = a1 + = ...
x2 1 1
a2 + a2 +
x3 1
a3 +
x4
or
x = [a1 , a2 , a3 , . . . ]

where the three dots indicate that the process is continued indefinitely.
√
Example 3.1.1. Expand 2 into an infinite simple continued fraction.

√
The largest integer less than 2 = 1.414 . . . is a1 = 1, so
√ 1 1
2 = a1 + =1+
x2 x2
Solving this equation for x2 , we get
√
2+1 √
x2 = √ √ = 2+1
( 2 − 1)( 2 + 1)
√
The largest integer less than x2 = 2 + 1 = 2.414 . . . is a2 = 2, so
1
x2 = 2 +
x3
where √
1 1 2+1 √
x3 = =√ = √ √ = 2+1>1
x2 − 2 2−1 ( 2 + 1)( 2 − 1)
At this stage we know that

√ 1 1 1
2 = a1 + =1+ =1+
x2 1 1
2+ 2+ √
x3 2+1
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 36

√ √
Since x3 = 2 + 1 is the same as x2 = 2 + 1, the calculations of x4 , x5 , . . . will a11
√
produce the same result, namely 2 + 1. Thus all the subsequent partial quotients will
be equal to 2, gives
√ 1
2=1+
1
2+
1
2+
2 + ..
..
or
√
2 = [1, 2, 2, 2, . . . ] = [1, 2]
√
In a reverse, we can get 2 from the infinite continued fraction [1, 2, 2, 2, . . . ] = [1, 2].
Let x = [1, 2, 2, 2, . . . ] = [1, 2]
1
i.e., x = 1 +
1
2+
1
2+
2 + ..
..
or
1
x−1=
1
2+
1
2+
2 + ..
..
Then
1
x =1 + !
1
2+
1
2+
2 + ..
..
1
=1 +
2 + (x − 1)
1
=1 +
x+1
from which we see that
1
x−1=
x+1
so,
(x − 1)(x + 1) = 1 or x2 = 2
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 37

Thus
√
x = [1, 2, 2, 2, . . . ] = [1, 2] = 2

Example 3.1.2. Find the infinite continued fraction expansion for

√
25 + 53
x=
22

√
Since 53 is between 7 and 8, the largest integer less than x is a1 = 1. Then
1
x=1+
x2
where √
1 1 53 − 3
x2 = = √ = >1
x−1 25 + 53 2
−1
22
The largest integer less than x2 is a2 = 2, so
1
x2 = 2 +
x3
where √
1 1 53 + 7
x3 = = √ =
x2 − 2 53 − 3 2
−2
2
The largest integer leass than x3 is a3 = 7, so
1
x3 = 7 +
x4
where √
1 1 53 + 7
x4 = = √ =
x3 − 7 53 + 7 2
−7
2
Thusx3 = x4 , , and so the last calculation will repeat over and over again.
Hence, the required expansion is
1
x=1+
1
2+
1
7+
7 + ..
..
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 38

or
x = [1, 2, 7, 7, . . . ] = [1, 2, 7].
√
25 + 53
Now, in a reverse, we can get from the infinite continued fraction [1, 2, 7, 7, . . . ] =
22
[1, 2, 7].
Let x = [1, 2, 7, 7, . . . ] = [1, 2, 7]
1 1
i.e., x = 1 + =1+
1 1
2+ 2+
1 y
7+
7 + ..
..
where
1 1
y =7+ =7+
1 y
7+
7 + ..
..
Then y satisfies the equation
y 2 − 7y − 1 = 0
Solving for y and noting that y > 0, we find that ,
√
7 + 53
y=
2
Hence √
1 1 25 + 53
x=1+ =1+ =
1 2 22
2+ 2+ √
y 7 + 53
which is the original value of x.

3.2 Convergents

The convergents to the infinite continued fraction x = [a1 , a2 , a3 , . . . ] are calculated in

pn
exactly the same way as before. The convergent cn = qn
is calculated by the same
formulas

pn = an pn−1 + pn−2 , qn = an qn−1 + qn−2 for all n > 1.

CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 39

√
Example 3.2.1. Calculate the first five convergents of 6.

√
The infinite continued fraction expansion of 6 is given by
[2, 2, 4, 2, 4, 2, 4, . . . ] = [2, 2, 4]

i.e., a1 = 2, a2 = 2, a3 = 4, a4 = 2, a5 = 4
Then
p1 = a1 = 2, q1 = 1
p2 = a1 a2 + 1 = 5, q2 = a2 = 2
p3 = a3 p2 + p1 = 22, q3 = a3 q2 + q1 = 9
p4 = a4 p3 + p2 = 49, q4 = a4 q3 + q2 = 20
p5 = a5 p4 + p3 = 218, q5 = a5 q4 + q3 = 89

or
i 1 2 3 4 5
ai 2 2 4 2 4
pi 2 5 22 49 218
qi 1 2 9 20 89
2 5 22 49 218
ci 1 2 9 20 89
√
5+1
Example 3.2.2. Show that x = 2
= [1, 1, 1, . . . ] = [1] and find the convergents.

√
5+1
Since x = 2
is between 1.5 and 2, the largest integer less than x is a1 = 1.
Then √
5+1 1
x= =1+
2 x2
where √
1 2 5+1
x2 = √ =√ =
5+1
−1 5−1 2
2
Since x = x2 , and so the last calculation will repeat over and over again.
Hence, the required expansion is
√
5+1
x= = [1, 1, 1, . . . ] = [1]
2
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 40

i 1 2 3 4 5 6
ai 1 1 1 1 1 1
pi 1 2 3 5 8 13
qi 1 1 2 3 5 8
1 2 3 5 8 13
ci 1 1 2 3 5 8

=⇒ pi ’s and qi ’s follow Fibonacci sequence.

Theorem 3.2.1.
(−1)n
cn − cn−1 = , n≥2
qn qn−1

pn
Proof. We know that the numerators pn and denominators qn of the convergents cn = qn

of the simple continued fraction [a1 , a2 , . . . , an . . . ] satisfy the fundamental recurrence

relation by 1.5.2
pn qn−1 − pn−1 qn = (−1)n , n≥2

irrespective of finite or infinite the continued fraction.

From this equation, upon dividing both sides by qn qn−1 , we get,

pn pn−1 (−1)n
− = , n≥2
qn qn−1 qn qn−1

(−1)n
=⇒ cn − cn−1 = , n≥2
qn qn−1


Theorem 3.2.2.
(−1)n−1
cn − cn−2 = , n≥3
qn qn−2
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 41

Proof. Clearly,
pn pn−2
cn − cn−2 = −
qn qn−2
pn qn−2 − qn pn−2
=
qn qn−2
(an pn−1 + pn−2 )qn−2 − (an qn−1 + qn−2 )pn−2
=
qn qn−2
an pn−1 qn−2 − an qn−1 pn−2
=
qn qn−2
n−1
an (−1)
=
qn qn−2


If we set n = 2 and then n = 3 in Theorem 3.2.1, and recall that the qn ’s are
positive, we see that
1 1
c2 − c1 = > 0, c3 − c2 = − <0
q 2 q1 q3 q2
which implies,
c2 > c1 and c3 < c2

Now, setting n = 3 in Theorem 3.2.2,

a3
c3 − c1 = >0
q3 q 1
Hence cl < c3 , and combining this results, we get

c1 < c3 < c2

Similarly n = 4 in Theorem 3.2.1,

1
c4 − c3 = >0
q4 q 3
gives
c4 > c3

and n = 4 in Theorem 3.2.2,

a4
c4 − c2 = − <0
q4 q2
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 42

gives
c4 < c2

Proceeding step by step in this fashion and combining these inequalities we obtain the
fundamental result

c1 < c3 < c5 < · · · < c2n+1 < · · · < c2n < · · · < c6 < c4 < c2

which leads to the theorem,

Theorem 3.2.3. The odd convergents c2n+1 of an infinite simple continued fraction form
an increasing sequence, and the even convergents c2 , form a decreasing sequence, and
every odd convergent is less than any even convergent. Moreover, each convergent
cn , n ≥ 3, lies between the two preceding convergents.
√
Example 3.2.3. Convergents of 2

√
The infinite simple continued fraction expansion of 2 is [1, 2, 2, . . . ] = [1, 2].
Then
i 1 2 3 4 5 6
ai 1 2 2 2 2 2
pi 1 3 7 17 41 99
qi 1 2 5 12 29 70
3 7 17 41 99
ci 1 2
= 1.5 5
= 1.4 12
= 1.416 29
= 1.413 70
= 1.414

Arranging them,

c1 < c3 < c5 < · · · < c6 < c4 < c2

i.e.,
1 < 1.4 < 1.413 < · · · < 1.414 < 1.416 < 1.5

Hence odd convergents forms an increasing sequence of numbers, all bounded

above by the convergent c2 = U . This will converge to a limit lU ≤ U . Since all
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 43

the odd convergents are less than all the even convergents, limit is also less than all the
even convergents.
Similarly, even convergents forms an decreasing sequence, all bounded below by c1 =
L, which will converge to a limit lL ≥ L. Since all the even convergents are greater than
all the odd convergents, limit is also greater than all odd convergents.

Theorem 3.2.4. Every infinite simple continued fraction converges to a limit l which is
greater than any odd conwrgent and less than any even convergent.

Proof. We have to prove that lU = lL = l

Substitute n = 2k in the Theorem 3.2.1,

1
c2k − c2k−1 =
q2k q2k−1

Also limit of {ck } is lL and limit of {c2k−1 } is lU .

By the definition of qn , {qn } is an increasing sequence, hence as k → ∞, q2k q2k−1
increases, hence
1
→0
q2k q2k−1
∴ c2k → c2k−1

=⇒ lL = lU = l

Theorem 3.2.5. If an irrational number x is expanded into an infinite simple continued

fraction [a1 , a2 , . . . , an , . . . ] according to the rules described, then the limit to which the
convergents c1 , c2 , . . . , cn , . . . of the fraction [a1 , a2 , . . . ,
an , . . . ] converge is the number x which gave rise to the fraction in the first place.
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 44

Proof. Let x be an irrational number ,

1
x = a1 +
1
a2 +
a3 + . . 1
. .+
1
an−1 +
xn
where xn is the rest of the fraction, which is also an irrational number and

1 1
x n = an + = an +
an+1 + . . xn+1
..

where
1
xn+1 = an+1 +
an+2 + . .
..
Since xn+1 is positive,
xn > an

Also xn+1 > an+1 , which implies

1 1
<
xn+1 an+1
1 1
∴ x n = an + < an +
xn+1 an+1
1
=⇒ an < xn < an +
an+1
or
1 1 1
> > (3.2)
an xn 1
an +
an+1
CHAPTER 3. EXPANSION OF IRRATIONAL NUMBERS 45

To prove x lies between cn and cn+1 , we compare the following expressions;

1
c n = a1 +
a2 + . . 1
. .+
1
an−1 +
an
1
x = a1 +
a2 + . . 1
. .+
1 (3.3)
an−1 +
xn
1
cn+1 = a1 +
a2 + . . 1
. .+
1
an−1 +
1
an +
an+1
1
Since a1 + is common for all of the three, its is enough to compare
a2 + . . 1
. .+
an−1
1 1 1
, , .
an x n 1
an +
an+1
By 3.2 and 3.3, x will always lie between two consecutive convergents cn and cn+1 that
is,
cn > x > cn+1 if n is even.

cn < x < cn+1 if n is odd.

Since all odd convergents are less than all even convergents, we are forced to the con-
clusion that
c2k−1 < x < c2k , k ∈ Z+

We know that as k → ∞, odd covergents and even convergents approach to l.

Hence l and x must be equal. 
Bibliography

[1] C. D. Olds, CONTINUED FRACTIONS, Random House and The L. W. Singer

Company, (1963).

[2] T.S. Bhanumurthy, A Modern Introduction to Ancient Indian Mathematics, New

Age International, (2009).

46