Euclidean Algorithm Explained Visually

(and the lock riddle solution)

Brett Berry
Nov 9, 2015 · 3 min read

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:

Image for post

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.

Image for post

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:

Image for post

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.

Image for post

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

Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

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).

Image for post

Next Lesson: Using Factors Trees to Find GCFs and LCMs

Thanks for reading!

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

Math Hacks

Tutorials with a fresh perspective.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store