Numbers: Their Tales, Types, and Treasures.

Chapter 10: Numbers and Proportions

 

10.3.EUCLID'S ALGORITHM AND CONTINUED FRACTIONS

In number theory, the method described in figure 10.3 is known as Euclid's algorithm for finding the greatest common divisor of two natural numbers a and b. It allows us to express the proportions between two numbers in the simplest possible way. To illustrate this, we will try to find the greatest common divisor of a = 1,215 and b = 360. We begin by writing

1,215 = 3 × 360 + 135, in general: a = k1 × b + r1,
360 = 2 × 135 + 90, b = k2 × r1 + r2,
135 = 1 × 90 + 45, r1 = k3 × r2 + r3,
90 = 2 × 45 + 0, r2 = k4 × r3 + r4.

The last nonvanishing remainder is 45. This is the common unit of 1,215 and 360, which is the greatest common divisor. Obviously, 1,215 is 27 × 45 and 360 = 8 × 45, and, therefore,

images

The algorithm also leads to another nice representation of the quotient of a and b:

images

The next step of the algorithm gives b = k2 × r1 + r2. Inserting this in the expression above gives us

images

Here, the last expression was obtained by dividing the numerator and denominator by r1. We continue by inserting r1 = k3 × r2 + r3, and so on:

images

This process can be continued until one of the remainders is zero. In the case of a = 1,215 and b = 360, the remainder r4 turned out to be 0, while k1 = 3, k2 = 2, k3 = 1, and k4 = 2. Thus, we obtain the continued-fraction representation

images

The coefficients in the continued-fraction expansion describe precisely how often the shorter segment fits into the longer segment in each step of the method described in figure 10.3. In that example, the coefficients of the continued fraction expansion are k1 = 2, k2 = 1, k3 = 2, and k4 = 2. We then get

images

There is another geometric interpretation of this method. Assume that we have a rectangle with length a and width b. Let us try to divide the rectangle into a grid of squares. For example, we start with a rectangle with sides a = 19 and b = 7, as shown in figure 10.4. The coefficients determined from Euclid's algorithm would describe how often the various squares would fit into the rectangle. There are k1 big squares (with side b), k2 of the next smaller size, and so on.

images

Figure 10.4: Tiling of a rectangle.