WOLFRAM|DEMONSTRATIONS PROJECT

The Euclidean Algorithm

​
first number (width)
second number (height)
step in algorithm
A graphical interpretation of Euclid's algorithm for calculating the greatest common divisor of two numbers: Given numbers
x
and
y
, draw a rectangle with width
x
and height
y
. 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
x
and
y
.