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
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
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
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.
|What if applet does not run?|
Copyright © 1996-2018 Alexander Bogomolny