Euclid's Algorithm is illustrated in the following window for us to work out the greatest common divisor of the two numbers M and N. We can write this more simply as gcd (M,N). In this example M=20 and N=32 and the algorithm works as follows:

We divide the two initial numbers then put the quotient at the top and the remainder underneath. The remainder then becomes the divisor. The algorithm ends when the remainder is zero and the divisor is the gcd (M,N) we were looking for.

1. Try out the algorithm with different numbers until you get used to how it works (you will be asked to do something more difficult than this in the exercises at the end of the unit). It works as follows:

   1. Click on the init button.
   2. Introduce two new numbers either by writing them in or using the arrows.
   3. Click on the animate button.
   4. If the algorithm has more steps than those that fit on the screen use the O.x control buttons to go back to earlier steps.
   5. Click on the init button and try the following example N=3234 and M=2078.