The Euclidean Algorithm: How and Why, Visually

We explain the Euclidean algorithm to compute the gcd, using visual intuition. You'll never forget it once you see the how and why. Then we write it out formally and do an example.

This is part of a playlist on GCDs and the Euclidean algorithm:

[ettkm]

Best explanation of the Euclid algorithm I found on YouTube, gives me intuition instead of just describing how to compute it or proving it.

[xatul]

Its been a month since I graduated engineering, and now is the day when I truly understand this algorithm

[stefanienix]

This is such a great video. I love how encouraging and soothing your voice is and I love that it has a handwritten vibe without doing that hand drawing the visuals that is in so many educational videos. All information flows so well that the only reason I'd rewatch is to notice what a great teacher you are. Thank you!

[fd]

Please make more videos! This is an amazing explanation, I love that you're teaching it through using visuals :)

[akshatkalra]

It's unassailably the most wonderful and comprehensive tutorial I've found on Euclidean Algorithm. I specially loved how you used the visual methods but also did not discount the mathy way of explaining things. Thank You, hope this reaches other people struggling to find the roots of this Euclidean algorithm.

[valeryjuli]

Thank you soo much for your videos! I always wanted to visually understand some math and algorithms but never found enough visual references on classic books, this is amazing :) Thanks!

[manarsalem]

This was mind-blowing to watch. I'm amazed at how you could convey everything so neatly and clearly.

[marklord]

I am interested in understanding how things work rather than memorization, and in less than a minute of the video, I knew it was special. Content such is this is absolutely vital. Thanks.

[luciepopova]

Thank you, that was actually the visualization I needed to see to finally understand the logic of the Euclidean algorithm!

[timetravellingblockhead]

This is excellent for giving intuition, understanding AND the ability to actually use it, thank you.

[bartomiejpotaman]

Youre a wonderful teacher. I mean it. You made it very suggestive what the answer is so that I could come up with it myself. Brilliantly done and I bet you - now it is mine forever!

[hidrogenhelium]

Nice, keep up the good work, hope this channel be great soon, Great explanation and even way to visual it

[kashikakhera]

This was very useful, appreciate the visuals you showed to prove, that was lacking in other videos that i saw. this will now stay in memory for long

[carlosraventosprieto]

I LOVED your video named rethinking the real line and now i saw this one and came in to your channel and saw that you are the same person!!!
i didnt subscribe 3 months ago but i do now with a smile on my face :)

[akshat.jaiswal]

Thanks! That's just the right type of video I was looking for. Keep up with the good work!

[akshaykaura]

At first, I didn't quite grasp why would the GCD remain same after we delete the smaller number from larger one (B-A). But it made sense this way:

Hint:
We are deleting pile A from pile B and then ask what's the new GCD of leftover pile B and the pile A? Well, just remember, the deletion is also made of new GCD as we just deleted pile A- hence the whole pile B and pile A have a new GCD ;) contradiction !


Explanation:
GCD is basically the largest chunk of stones that will divide both piles in some number of parts, say- xa and xb. So, pile A has xa number of GCDs and pile B has xb number of GCDs (largest chunks common for both).
=> A = g . xa and B = g . xb (Imagine them as bigger balls that make up the pile)
Now, we remove just one copy of pile A from B. This means:
=> B - A = g . xb - g . xa

For a moment, let's assume, the common chunk size of A and B-A, could maybe get bigger after deletion- to say g' (read: g dash)
=> B - A = g' . x' and A = g' . xa'
This means, the leftover of pile B is made of g' size chunks with count as x' and pile A is made of g' size chunks with count as xa'.

But, here's the catch: the deleted pile A from pile B must also be made of g' size chunks with count as xa'. That means:
=> deleted pile A + left over pile B = the original pile B
=> g' . xa' + g' . x' = pile B
=> g' (xa' + x') = pile B
So, the pile B is made of g' size chunks AND pile A is also made of g' size chunks! A common divisor for A and B!
What's the largest common divisor for A and B?
=> The GCD(A, B) = g

Hence, g' = g, the original GCD of A and B!

[hrushith]

Really the best explanation. I wish this channel grows.

[viniciusfriasaleite]

Looks like the pile B has 57 stones on the image... but that doesn't change the explanation, it's very good

[ianweckhorst]

Thank you so much for insisting that I figure it out myself, I didn’t get to do that for the quadratic formula, which I still don’t get and just memorize, I think this is what I wanted to do so long ago and I think this helped me go through those motions

[compucademy]

To do this you have to know what the gcd is in advance, and this is just confirmation it seems. My challenge is how to show visually what d (an arbitrary divisor of both numbers) can be when we don't know in advance. Sure if we know for example that two is a common divisor we can group everything in 2s, but how do you represent grouping everything in a arbitrary group size, until the gcd, or any common factor for that matter, is found?