The Euclidean Algorithm
The Euclidean Algorithm
A graphical interpretation of Euclid's algorithm for calculating the greatest common divisor of two numbers: Given numbers and , draw a rectangle with width and height . If this rectangle is divided into squares as shown in the Demonstration, then the width of the smallest square (shown in red) is the greatest common divisor of and .
x
y
x
y
x
y