Euclidean Algorithm Explained Visually

(and the lock riddle solution)

Seeing that this algorithm comes from Euclid, the Father of Geometry, it’s no surprise that it is rooted in geometry. Today we’ll take a visual walk through the Euclidean Algorithm and hopefully gain some useful insights.

Walking Through the Algorithm Visually

To warm up let’s find the greatest common divisor of 16 and 38 using a 16x38 unit rectangle:

Step 1: rewrite 38 as a product of 16 and a whole number plus the remainder.

Pictorially this translates into finding out how many 16x16 unit squares fit in the rectangle.

Two 16x16 squares fit in the rectangle leaving us with a 16 by 6 unit rectangle unshaded.

These values are represented in the first formal step of the algorithm:

Step 2: Repeat the process again by divvying up the unshaded region with the largest squares we can make.

In this case we can fit two 6x6 blocks in the unshaded area.

And here’s the next formal step of the algorithm:

This yields another unshaded rectangle this time with an area of 4x6 units.

Step 3: Reset the algorithm to find the greatest common divisor of 6 and 4. E.g. fit one 4x4 square in the remaining 4x6 unshaded rectangle.

Step 4: Lastly, we have a 4x2 rectangle left unshaded. We can fit two 2x2 squares in the 4x2 region. This is our final step as it leaves us with no remainder.

Now that the original 16x38 unit rectangle is completely shaded, we have come to the end of the algorithm. The picture shows us visually that the largest square that can cover the entire 16x38 rectangle is a 2x2 square.

This means that the greatest common divisor of 16 and 38 is 2.

Now you can perform the Euclidean Algorithm without the pictures simply by following the mathematical pattern.

The Lock Riddle Solution

from the last post

In the last post, I posed a riddle for you to ponder. The key to the riddle is to interpret the following statement literally:

“…even if you were able to change the numbers at the rate of one per second without rest, it would still take you a hundred years to hit the right combination.”

Therefore if we assume the prisoner is entering combinations in order beginning with 0000000001, the correct lock combo is the number of seconds in 100 years (ignoring leap years).

Next Lesson: Using Factors Trees to Find GCFs and LCMs

Thanks for reading!

Please click the ❤ to let me know you learned something new!