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

.