The Euclidean Algorithm: How and Why, Visually
Вставка
- Опубліковано 25 лип 2024
- 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:
• GCDs and Euclidean alg... - Наука та технологія
Best explanation of the Euclid algorithm I found on UA-cam, gives me intuition instead of just describing how to compute it or proving it.
Thank you!
Same. :)
This is brilliant. Please continue to make more such videos. This is how science and math must be seen.
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.
WOW. You explain stuff in such an intuitive manner
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!
Please make more videos! This is an amazing explanation, I love that you're teaching it through using visuals :)
This should be first hit for Euclidean algorithm
This was mind-blowing to watch. I'm amazed at how you could convey everything so neatly and clearly.
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!
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.
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! :)
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 !!!!😢😢😢😢😢😢😢.
This is excellent for giving intuition, understanding AND the ability to actually use it, thank you.
Thanks! That's just the right type of video I was looking for. Keep up with the good work!
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 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
I really like your channel. Your method of exposition is exceptional.
Thank you, that was actually the visualization I needed to see to finally understand the logic of the Euclidean algorithm!
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.
Nice, keep up the good work, hope this channel be great soon, Great explanation and even way to visual it
Really the best explanation. I wish this channel grows.
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!
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 :)
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.
Amazing video! I personally think this explanation is much better than the ones shown on AwesomeMath L4
Such a good teacher! Seriously!
You are an inspirational teacher !
Perfect Explanation, Thank you!
Underrated video. Thanks a lot!
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
What a beautiful time to be alive.!
Excellent explanation. Thanks!
Excellent video.
Very helpful video! thanks!
best video on this topic by far
This is pretty visual and intuitive, thank you.
Bruh I was already impressed but then you went with the speed-up portion and took it to a new level of impressive!
Thank you so much for making us think
Absolutely amazing😍
really love it wish that you make more videos
Thank you! This was really helpful :))
Amazing!
Way to teach.❤
Awesome, thanks a lot!
you are a legend
Looks like the pile B has 57 stones on the image... but that doesn't change the explanation, it's very good
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 UA-cam videos because you can't fix them! :) Anyway, thanks for pointing that out.
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!
Amazing
you are great. i love you
love it;❤
perfecto !!!
Minor point: in your discussion of the Division Algorithm, you need to use |a| rather than a, given that you're allowing a,b \in \mathbb{Z}
Thanks.
Thanks
This is great. Wondering how did you come up with this way of visualizing and solving problems? Are there any references that you would like to share?
I finally get it!
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.)
Euclid from the heavens: Ohh mistress with a beautiful soul, may god blesseth thee.
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?
Love you
Prayers ....
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 UA-cam 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.
Well, we ARE just "confirming" the gcd when we compute it. It already exists!
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.
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?
Sorry didnt watch till end of vid where you explain this. My bad
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.
starts from 7:19 a bigger problem gcd(a,b) -->gcd(b, a-b) according to your algorithm, but you put gcd(a, a-b).
Great stuff. However, it would have been useful to show an example where there are no common factors except for 1.
our explanations are similar except I cut the box Into Identical sections
Basic question: What is the operator / symbol "|" displayed in the proof at 13:20?
Ok found the answer later in the video. a | b means a is an integer divider of b.
@@pedrorivera4405 You are correct! (I think the timestamp is closer to the 7-8 minute mark?)
@@pedrorivera4405 I had the same doubt, thank you !
Rather than the division algorithm you might want to introduce the modular algorithm.
❤
This is the first explanation I have seen that describes the deeper understanding. Plus voice is very calm.
I think you have a typo: the 5 in the factorization of b should have exponent 3 not 2 :D
And lovely video!
@@hannesstark5024 Thank you! I'm sorry about the typo -- you are right about that!
I see the proof for a common divisor, but where is the proof it is a largest possible common divisor?
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.
@@jaideepshekhar4621 But why we are sure that the first numbers we get is indeed the highest? Maybe there is another value we have never seen?
@@BestHolkin Exactly the same thought! Glad someone said it!
I don't understand shit she said . 😅
Makes no sense. Not clear at all why there aren't two groups of 3 remaining in the end, for example.
Why would there be 2 groups of 3 in the end? The pattern is still there, and can be removed.
Thanks.