## 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* = *k*_{1} × *b* + *r*_{1},

360 = 2 × 135 + 90, *b* = *k*_{2} × *r*_{1} + *r*_{2},

135 = 1 × 90 + 45, *r*_{1} = *k*_{3} × *r*_{2} + *r*_{3},

90 = 2 × 45 + 0, *r*_{2} = *k*_{4} × *r*_{3} + *r*_{4}.

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,

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

The next step of the algorithm gives *b* = *k*_{2} × *r*_{1} + *r*_{2}. Inserting this in the expression above gives us

Here, the last expression was obtained by dividing the numerator and denominator by *r*_{1}. We continue by inserting *r*_{1} = *k*_{3} × *r*_{2} + *r*_{3}, and so on:

This process can be continued until one of the remainders is zero. In the case of *a* = 1,215 and *b* = 360, the remainder *r*_{4} turned out to be 0, while *k*_{1} = 3, *k*_{2} = 2, *k*_{3} = 1, and *k*_{4} = 2. Thus, we obtain the continued-fraction representation

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 *k*_{1} = 2, *k*_{2} = 1, *k*_{3} = 2, and *k*_{4} = 2. We then get

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 *k*_{1} big squares (with side *b*), *k*_{2} of the next smaller size, and so on.

**Figure 10.4: Tiling of a rectangle.**