Euclids - Graphical display of Euclid's algorithm

by Richard Taylor

Euclids displays Euclid's algorithm in a fascinating visual way. You may well have come across Euclid's algorithm before, even if the last time was at school. It is an algorithm which finds the highest common factor of two given numbers - that is, it finds the largest number which divides into both of them exactly. This program should enable you to see it in a new - graphical - light.

Click on the Euclids icon in the RISC User master menu to run the program, and the screen will clear. At the top of the screen the current values for 'm' and 'n' are displayed. These are the two 'given' numbers to which Euclid's algorithm is to be applied, and they may be altered. Beneath this, the calculations involved in the algorithm, the related 'continued fraction' and most interestingly, the geometrical display are shown - all of which will be explained in a moment. (Those readers familiar with Euclid's algorithm may wish to go straight to the explanation of the graphical display.)

Euclid's algorithm is probably best illustrated by an example. Let us consider the two values for 'm' and 'n' to which the program defaults - 51 and 42.
We see -

   51 = 1 x 42 + 9     (1)
   42 = 4 x  9 + 6     (2)
    9 = 1 x  6 + 3     (3)
    6 = 2 x  3 + 0     (4)

At each stage the remainder of a division is found. The first equation tells us that 51/42 leaves a remainder of 9. Equation (2) also tells us the remainder of the division. But this time it is that of 42 (which was the divisor of the previous division) divided by 9 (the remainder of the previous division). We see that this new remainder, of 42/9, is 6. In the same manner we note that the remainder of 9/6 is 3 and that of 6/3 is 0. We have now reached a zero remainder where we stop. The highest common factor of our original two numbers is simply the last non-zero remainder, in this case, 3. (Readers who wish see a proof of this are referred to H. Davenport's book, see reference in RISC User Magazine 8:9.)

The list of calculations above also allows us to find what is known as the continued fraction for 51/42 (our first number divided by the second - ie. m/n). What follows is an explanation of their creation - you may wish to skip this for the time being, and go on to the description of the graphical display.

We start by dividing equation (1) by 42 :

   51/42  =  1 + 9/42  =  1 + __1__       (5)
                                             42/9

Moreover, if we divide equation (2) by 9 we get :

   42/9   =  4 + 6/9   =  4 + _1_         (6)
                                            9/6

So substituting into equation (5) above we see that :

   51/42  =  1 + __1___                   (7)
                        4 + _1_
                              9/6

We continue in a similar manner, dividing equation (3) by 6, to get a substitution for 9/6 which we put into equation (7) above to find that :

   51/42  =  1 + __1____
                         4 + __1__
                              1 + _1_
                                     2

This is the complete continued fraction for 51/42. Note that the series of numbers along the bottom diagonal, here 1, 4, 1, 2, are the quotients (whole parts) of the divisions in Euclid's algorithm. (ie. they are the numbers directly after the equals sign in each of the equations (1) to (4).) A similar continued fraction may be generated for any two numbers - which you will see as you alter the values of 'm' and 'n' using the program.

If this seems somewhat complex, we can also display these results in a remarkable geometric pattern, which should hopefully make things easier to understand. We start with a rectangle which has sides of length 'm' and 'n' - here 51 and 42. A line is drawn so that we have square of size 42 at the left of the rectangle. This leaves a smaller rectangle of width 9 on the right. See how this relates to equation (1) : 52 = 1 x 42 + 9.

Squares of size 9 are then drawn up this smaller 9x42 rectangle. A total of 4 may be fitted in at which point we are left with a rectangle of height 6 at the top. Again see the relation to equation (2) : 42 = 4 x 9 + 6

This is continued twice more, with one square of size 6 and two of size 3 being fitted in, until the original rectangle is completely made up of squares. Note that the series formed by the number of squares of each size, here 1, 4, 1, 2, is the same as the one mentioned above in the context of continued fractions. Moreover, the sizes of the squares themselves are equal to the successive remainders that were calculated above. Thus the size of the smallest square, at the top right of the original m by n rectangle is equal to the highest common factor of m and n.

The rectangle, displayed in blue on the screen, may be altered by dragging by its top right corner using the mouse, thereby altering the values of 'm' and 'n'. Watch how the patterns in the rectangle change as it is made larged and smaller. The displayed calculations of Euclids algorithm and the continued fraction also change as the rectangle moves.

The cursor keys may also be used to enable more exact alteration of 'm' and 'n'. The left and right cursor keys change 'm' while the up and down keys change 'n'. The space bar may be used to cycle through the three display modes.   The first (and default) mode displays both the calculations and the rectangle at the same time while the other two show them seperately. This is useful when there is overlap on the screen.

There are many interesting relationships between pairs of numbers that may be observed here. You may wish to alter 'm' and 'n' to successive numbers in the Fibonacci series (a series where each term is the sum of the previous two - it starts 1, 1, 2, 3, 5, 8,....). The largest pair possible using this program is 144 and 89 where you will see that the continued fraction contains all ones apart from one two at the end. And the rectangle is filled by single squares each of which have a size that is a term in the Fibonacci series.


 Copyright RISC User, 1995
