Chapter II

Formation of Continued Fractions

2.1 Expansion of a Real Number into a Continued Fraction

2.1.1 Algorithm of Expansion into a Continued Fraction Forget for the time being the decimal system. The Russian mathematician Nikolai Nilolaevich Luzin used to say in his lectures that the advantages of the decimal system are zoological, not mathematical. If we had eight fingers on our two hands instead of ten, mankind would operate in the octal system. Indeed, the decimal system is very convenient in practice, but it is inappropriate for a discussion of theoretical aspects of arithmetic.

Forget about any decimal and positional number system, that is, take Archimedes place and ask yourself: What would be the most natural approach to estimating a real number?

This question is answered without hesitation: The first step is to indicate the integers between which our number lies. For example,

61/27 lies between 2 and 3,
Ö 2 lies between 1 and 2,
p lies between 3 and 4.

Naturally, it is sufficient to indicate only the lower bound:

61/27 = 2 + x (0 < x< 1),
Ö 2 = 1 + y (0 < y < 1),
p = 3 + z (0 < z < 1).

Note that these estimates are not tied to any specific notation of integers, that is, to a specific number system!

Continue with the number 61/27. The estimate two plus something is too rough and represents only a first approximation. If you want to take the second step, you have to estimate the make-weight x. Since x is less than 1, it is logical to represent it by a fraction with numerator 1 (again recall acting natural, but this is the last time we shall do so):

61/37 = 2 + 1/x₁.

Now, x₁ is larger than unity and you repeat the familiar steps: Single out the integral part of the number, etc. Study carefully the following layout of these steps:

.

The expression

where a₁, a₂, ··· , a_s are natural numbers* and a₀ is a natural number or 0, is called a continued fraction.

* Recall that the natural number are 1, 2, 3, ··· , 0 is not included in the set of natural numbers.

The numbers a₁, a₂, ··· , a_s are called the terms of the continued fraction. You say that you have expanded the fraction 61/27 into a continued fraction.

We will employ this algorithm frequently. It involves two alternate steps:

Step 1 Isolate the integral component of the number, that is, write it as the sum of an integer and a remainder which is less than unity.

Step 2 Represent the remainder as 1 divided by a number larger than 1. Apply Step 1 to this denominator, etc.

However, before developing the theory of continued fractions, we will answer three questions.

2.1.2 Notation for Continued Fractions

Question 1 Is not this notation for continued fractions too complicated? The first example led to a three storeys fraction; for a twenty storeys fraction, a book's page will be too small!

Hence various notations were developed. We will employ

The semicolon (;) emphasizes the special role of the integral part a₀, which differs from that of the other terms. While its role is special, it is not more important. In this particular case, it is rather less important.

2.1.3 Expansion of Negative Numbers into Continued Fractions

Question 2 How do you expand a negative number into a continued fraction?

You can employ one of two alternatives:

1. Place the minus sign in front of the entire fraction; for example,

2. Allow negative values of a₀, keeping a₁, a₂, ··· , a_s positive at all times. For example,

We will use the second version, whence, from now on, a₀ is an arbitrary integer while a₁, a₂, ··· , a_s are natural numbers.

Apart from this remark, negative numbers will not enter into the development of the theory. It can be obtained by adding a certain negative integer to a positive number. In order to examine the arithmetical nature of the number - 61/27, you can study 20/27 and then add 3 units to it.

2.1.4 Examples of Non-terminating Expansion

Question 3 Will the process of expansion of a number a into a continued fraction inevitable end? No, it may turn out to be infinite. Consider some examples.

Example 1 Expand Ö 2 into a continued fraction.

You find that x₂ = x₁, whence every step is repeated from this point onwards: x₃ = x₂, x₄ = x₃, ···. Step by step, you obtain

As long as you give a finite expression for Ö 2 (involving an irrational x₂), you can use the equality sign. If this process is continued indefinitely, you find

Ö 2 ~ [1; 2, 2, 2, ···],

that is, the number Ö 2 corresponds to a non-terminating continued fraction. You cannot place the equality sign between Ö 2 and the non-terminating continued fraction [1; 2, 2, 2, ···], because you cannot as yet transform the notations into each other from both directions. So far, the symbol of a non- terminating continued fraction lacks meaning, This problem is solved in Chapter VI.

Example 2 In geometrical problems, you can expand a geometrical quantity in a continued fraction without knowing its numerical value. For example, find the ratio of the base to a side of an isosceles triangle with the vertex angle 108º.

The angles of the triangle ABC (Fig. 6) are 108º, 36º, 36º. Mark off BB₁ = b (obviously, b can be marked off only once, because a < 2b). You find

a/b = BC/BB₁ = (BB₁ + CB₁)/BB₁ = 1 + B₁C/BB₁) = 1 + 1/x₁;
x₁ = BB₁/B₁C = AC/ B₁C.

However, the triangle B₁AC is similar to the initial triangle ABC. The first line above determined the ratio a/b of the base to the side. The second line represents the same problem, because x₁ is the ratio of the base to the side in a triangle of the same shape. The process cannot terminate, because the first step resulted in a reproduction of the initial situation. You can write

a/b ~ [1; 1, 1, 1, ··· ].

Similarly, you can show that

b/a ~ [0; 1, 1, 1, ··· ].

We shall return to this result at the end of 4.2.2.

Example 3 Expand the ratio of the diagonal of a square to its side into a continued fraction. This task is more complicated than the second one. We returned there to the initial state after the first step, while here you require two steps before this happens.

If you assume that d/a = Ö 2, this example coincides with Example 1. But the expansion of the ratio d/a into a continued fraction can be obtained geometrically without any numerical information.

Initial situation: Mark off the side along the diagonal; this can only be done once! You find (Fig. 7):

d/a = CA/CB = (CB₁ + B₁A)/CB) = 1 + 1/x₁;
x₁ = CB/B₁A = AB/AB₁.

Next erect B₁B₂ ^ AC. The BB₂ = B₁B₂ (You must prove this!) Now complete the triangle AB₁B₂ into a square (merely for the sake to make everything clear; this is not required by the proof) and mark off AB₁ along BA. Having marked it off once, you obtain BB₂, the remainder being B₂A. Next, mark off AB₁ along B₂A; this repeats the initial situation: The side of a square is marked off along the diagonal, whence the process is infinite, that is,

x₁ = 2 + 1/x₁;
d/a ~ [1; 2, 2, 2, ···].

It is readily shown that

a/d ~ [0; 2, 2, 2, ···]

(cf. 4.2.2).

2.2 Euclid's Algorithm

2.2.1 Euclid's Algorithm The preceding section dealt with the algorithm of the expansion of real numbers into continued fractions. Such an algorithm comprised two alternative steps: 1. The separation of the integral part of a number, 2. the presentation of the remainder (which is less than unity) as a reciprocal of a number greater than unity. This algorithm is a particular case of Euclid's algorithm, used widely in mathematics.

In order to illustrate this algorithm, find the greatest common divisor of two natural numbers (abbreviated GCD) .

Let p and q be natural numbers. Euclid's algorithm involves the steps*:

* If p < q, then a₀ = 0. This does not affect the process.

This process is described by the formulae

Explanation If the dividend and the divisor are integers, then the remainder may be zero. Why then do we exclude the equality sign on the left hand side, that is, why do we write, for example, 0 < r₁ < r₂ instead of 0 £ r₁ < r₂? Because if it so happens that r₁ = 0, this equality terminates the sequence. The algorithm cannot but stop, because the remainders r₀, r₁, r₂, ··· are non-negative integers and each next one is less than the preceding one, whence the remainder r will necessarily become zero at some step.

The equalities (3) can be rewritten:

where r_s-1 is the required quantity: The GCD of p and q.

Each of the equalities, except for the last one, is an improper fraction presented as a sum of an integer and a proper fraction. Note that the left hand side of each equality ( beginning with the second one) is the reciprocal of the proper fraction of the preceding equality. Hence we can eliminate successively all r_i. Replacing the fraction r₀/q in the first equality by its expression from the second equality, you find

The fraction r₁/r₀ in this equality is now replaced by its expression from the third equality

Continuing this process, you eventually expand p/q in a continued fraction. However, there is no need to repeat each time these substitutions. Indeed, a₀,a₁,a₂, ··· , a_s are the terms of the required continued fraction. You only have to remember the rule:

In order to expand p/q in a continued fraction, apply Euclid's algorithm to the numbers p and q. The quotients obtained at the successive stages are the terms of the required continued fraction.

Example Expand 61/27 in a continued fraction.

whence

61/27 = [2; 3, 1, 6].

2.2.2 Examples of applications of Euclid's algorithm Euclid's algorithm may not only be used to find the GCD of two natural numbers. Let p and q be elements of an arbitrary set in which division with remainder* has been defined. You can then apply Euclid's algorithm.

* This means that each ordered pair of elements p and q (p is the dividend and q the divisor) is put in correspondence with an ordered pair a and r (a is the quotient and r the remainder) which satisfies the conditions p = aq + r, r < q. Obviously, the operation of multiplication and the relation less than must also be defined on this set.

For example, if p and q are segments of the number line, Euclid's algorithm can be applied to find their common measure. If p and q are commensurate, Euclid's algorithm terminates and the segment r_s-1 [cf. (3)] is their common measure. In fact, it follows from the last equality in (3) that r_s-1 is contained in r_s-2 an integral number of times. Substitution of r_s-2 into the last but one equality yields

r_s-3 = a_s-1a_sr_s-1 - r_s-1= (a_s-1a_s + 1)r_s-1.

Hence r_s-2 is also an integral multiple of r_s-1. If you thus climb the ladder of (3) step by step, you reach the first two lines, that is, you prove that both p and q are integral multiples of r_s-1, and therefore r_s-1 is their common measure.

Moreover, Euclid's algorithm yields the terms of the continued fraction which corresponds to the ratio p/q. If the segments p and q are incommensurable, Euclid's algorithm does not stop and the numbers a₀; a₁, a₂, ··· are the terms of the non-terminating fractions which represents the rtio p/q.

Euclid's algorithm can also be applied to polynomials of a single variable x. The phrase less than then means that it is of lower power. By means of the algorithm, you can find the GCD of two polynomials; however, this result does not affect the present topic.

2.2.3 Summary An algorithm has been outlines (in its two versions) which permits to expand any real number a in a continued fraction, that is, to find a continued fraction corresponding to that number.

If a is a rational number, it corresponds to a terminating continued fraction. The calculations can then be carried out in reverse order, that is, you can find the value of the continued fraction. For example,

Hence, instead of the sentence the continued fraction [2; 3, 1, 6] corresponds to the number 61/27 you can say the number 61/27 equals the continued fraction [2: 3, 1, 6] or, to be even more precise, you can say that 61/27 and [2:3, 1, 6] are two different notations for the same number.

However, if a is an irrational number, the situation changes completely. Then the correspondence between a and the continued fraction is defined in one direction only; the number a corresponds to a non-terminating continued fraction, but not vice versa. You cannot determine a non-terminating continued fraction by the same procedure as has been used to calculate [2: 3, 1, 6]. Hitherto, you do not know the meanings of non-terminating continued fractions.

This problem must still be solved. Chapter 5 shows how to give a meaning to non-terminating continued fractions. Remember while reading Chapters 3 and 4 that so far we not know this.

last next