What a woman.. Your visual teaching with a concise explanation of voice literally broke the algorithm into every piece to be understood by everyone including me.. Thanks a lot from Korea.!
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!
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.
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.
I wish I could say thank you in person. I am a Mechatronics Engineering Student and we are Studying the Routh-Hourwitz Criterion in Control Systems. I'm trying to understand this so I can understand the proof of the Routh-Hurwitz criterion better. I have to say, you are part of the people that make my degree worthwhile. Thanks so much for what you do. Thanks for not giving up on prooving mathematial facts. Thanks for not giving up on intuition. Thanks for not obscuring mathematical concepts . Thanks for making it accessible. Thank you. Thank you. Thank you !!!!😢😢😢😢😢😢😢.
AMAZING explanation. I don't think I'll ever need to study Euclidean or Extended Euclidean again, because this will always remain in my mind. Thank you so much! :)
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!
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!
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!
Oddly enough, I learned about the Euclidean algorithm through Stern's Diatomic array, where you can find any pair of coprime positive integers and trace a step-by-step path (that is equivalent to the Euclidean algorithm) through the array back to the pair 1, 1.
Yes! These are very related ideas, and some of my favourites. I have a video on Lehmer's Factor Stencils that talks a bit about the Farey fractions and how it relates to continued fractions, which are really just a form of Euclidean algorithm.
Oh. My. Goodness. You know, I studied a lot of math in college when I was young (Calc 1 & 2, Abstract Algebra 1 & 2, Linear Algebra, Functional calculus, etc., I can't even remember all the courses), so I am no patzer although I am not a professional mathematician... This BLEW MY MIND. THANK YOU. I love math.
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 :)
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
Oh! Well, 57 is divisible by 3, so the universe is not broken, I probably just counted wrong when labeling the picture... darn. It's so painful making mistakes in RU-vid videos because you can't fix them! :) Anyway, thanks for pointing that out.
Hopefully someone can explain this in an intuitive way, but why is the remainder the next candidate for the GCD? How do we know we didn't skip some number n which is remainder < n < smaller number?
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?
Interesting question. The algorithm has to "discover" what the gcd is, so there can't really be a way to see the gcd until after the algorithm plays out (unless, as you say, we guess it in advance). There is another interesting way to do the algorithm by nesting squares in a rectangle (you'll find videos of it on RU-vid and I might make a video about it too). This has the advantage that the entire algorithm is contained in one picture (instead of a series of steps like in my video above). So in some sense the gcd is shown in that picture.
Play the video backwards. If the algorithm ended with pile A = pile B, then everything that was deleted was built out of copies of that final pile size too, so that final size must be a divisor of both original piles. It's less obvious to me that the common divisor found must be the largest one.
Hmm. Well, this is just designed to show why the algorithm works (essentially because, by definition, call gcd(a,b)=g, both a and b are composed of "a number of whole groups containing g number of elements" (so to speak), so all the time you are subtracting things that come in groups of g elements from things that come in groups of g elements, so obviously you always end up with a smaller thing that comes in groups of g elements). You certainly do not need to know the gcd beforehand to apply the algorithm
This is a nice explanation and beautifully illustrated. However, since I am a mathematician myself, I cannot help but to pick some nits. You might have mentioned that the original version, with just subtraction and stopping when both piles are of equal size, is the original version by Euclid. Because despite it being named after him, Euclid did not use Euclidean division in his description of his algorithm. And he did not stop at 0 because the Greeks did not have 0. Going to your description of the slow version (7:56), as we _do_ know about 0 and negative numbers, and your preceding statement explicitly allows any values in Z, I thought you should have been more specific than the ordering condition (1): you should also state the a (and therefore b as well) is _positive_ (it is interesting to see what happens when this is violated, but it is not a pleasant sight). And I found it a pity that your termination condition is not kept to be a=b as it was before, as this makes step (2b) unambiguous (as you stated it, one might or might not want to swap two equal values, even though it clearly makes no difference) and also step (3) easier: when a=b, the gcd is a (and also of course b). And you don't need to mention zero, just like before. Besides, your rules do not take heed of the fact, obvious from inspection, that any (first) occurrence of zero must be in the second position. I think that the only reason to introduce these changes is anticipation of the speedier version, since Euclidean division as usually defined has a hard time hitting the case a=b on the head (since the remainder must be strictly less than the divisor). The fact that now any zero clearly goes to the _second_ place confirms my suspicion that the earlier version was already formulated with this change in mind. That seems to me to be pedagogically a bad choice; I always get thrown off my understanding of an argument when suddenly it gets too slick, especially if that slickness is not announced or explained. The condition a>0 is also conspicuously absent in your statement of the (Euclidean) Division Algorithm, making it false.
Nicely done! The only thing that initially confused me was the termination criterion in the game at the beginning. Should we stop when one pile is reduced to zero elements or when the piles have the same number of elements. (Both work, I guess, but the first rule is probably better as it correlates well with the Euclidean algorithm.)
You showed a visual proof with the triangles showing that it leaves 3 if the gcd is 3 never breaking part the groups which the amount would be the gcd, but I still dont understand why that works or happens, you just showed that it did, but i don't understand why subtracting it from each side leaves the gcd.
Great vid! Just a question though. Wouldn't the assumption be that gcd(a,b) = gcd(a,b-na) instead of gcd(a,b) = gcd(a,b-a) since you are subtracting a multiple, n of a from b instead of just subtracting 1*a from b?
Well, if you look, we diminish the piles until we've found the first number that divides both of them. If you proceed in the algorithm, you will only get smaller divisors, and hence, the first number you get is the largest divisor. Note that 1 marble is also a divisor, but we stopped at 3 first.
