Euclid's algorithm is a famous procedure for finding the gcd, i.e., greatest common divisor (factor) of two integers. The idea is pretty simple. If N = M×s, with N, M, s, positive integers, then any divisor of M is also a divisor of N, making M their greatest common divisor:

when N = M×s + R (where all four are positive integers), then every common divisor of M and M is also a divisor of R. Actually, any common divisor of any pair of these three numbers is a divisor of the third; so that, with R ≠ 0,

Euclid's algorithm is based on the observation that taking R to be the remainder of the division of N by M makes R < M. Which means that the task of finding the gcd of N and M, with M < N, can be reduced to the same problem but with smaller numbers, M and R. Doing that we'll get another remainder even smaller than R and so on until the remainder becomes 0. This is assured since on every step we are dealing with smaller numbers, but a decreasing sequence of integers is necessarily finite. In the case of the remainders in Euclid's algorithm the last term must be 0 for, otherwise, one would be able to perform at least one more step of the algorithm.

The applet below illustrates Euclid's algorithm. The two numbers on top are modifiable digit-by-digit. Click a little off the vertical midline of the digit you wish to modify. (For a faster action just drag the mouse up and down.) When the box "Autonomous digits" is checked, trying to increase, say, 9 in 19 will result in 10, otherwise it will be 20. The number of digits is also controlled at the bottom of the applet.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Buy this applet What if applet does not run?

Copyright © 1996-2010 Alexander Bogomolny