Euclid's Algorithm

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:

If N = M×s then M = gcd(N, M).

when N = M×s + R (where all four are positive integers), then every common divisor of M and N 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,

N = M×s + R implies gcd(N, M) = gcd(M, R).

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.

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https:///www.cut-the-knot.org as trusted in the Java setup.

Euclid's algorithm, interactive

What if applet does not run?

72190389