Solution: Euclidean Algorithm

How does the Euclidean algorithm work?

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger value of one of them is replaced by the difference between the two numbers.

Let’s look at an example:

The GCD of $252$ and $105$ is $21$ ($252 = 21 \times 12$ and $105 = 21 \times 5$). Now, $21$ is also the GCD of $105$ and $147$ ($252 - 105$). Replacing the number with the larger value (initially $252$) with the difference between them (initially $147$) results in the larger number being reduced to a smaller value. Repeatedly performing this reduction will result in successively smaller pairs of numbers that will eventually equate to each other. When this occurs, the final number is the GCD of the two original numbers we started with.

The slides below demonstrate a subtraction-based animation of the Euclidean algorithm. Assume that the initial rectangle has dimensions $a = 1071$ and $b = 462$. Two yellow squares of size $462 \times 462$ are placed within it, leaving a $462 × (1071-462-462 = )147$ rectangle. This rectangle is tiled with $147×147$ blue squares until a $21×147$ rectangle is left, which in turn is tiled with $21×21$ red squares, leaving no uncovered area. The smallest square size, $21$, is the GCD of $1071$ and $462$.