Wow, this video is simply amazing, not only do you help us visualize the algorithm but you also make it intuitive to the point where you can derive it yourself. Thank you so much! I will be sure to check your videos out for future concepts!
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.!
Best explaination ever made for this topic by just one joing lines of a traingle you explained the smallest detail. Thank you very much for this it was so much helpful.
This + thinking gives refreshing perspective on what the heck my lecturer been trying to get to me. It's always the fact that you need to process raw information first, before understanding it normally.
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!
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 !!!!😢😢😢😢😢😢😢.
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.
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.
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.
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!
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! :)
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.
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!
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 TH-cam videos because you can't fix them! :) Anyway, thanks for pointing that out.
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 :)
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?
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.
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.)
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.
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 TH-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.
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
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.
Best explanation of the Euclid algorithm I found on TH-cam, gives me intuition instead of just describing how to compute it or proving it.
Thank you!
Same. :)
@@ProofofConceptMathThere is a 90s Canadian Movie called Cube where I'm pretty certain this method is how the survive. Worth checking out either way.
Wow, this video is simply amazing, not only do you help us visualize the algorithm but you also make it intuitive to the point where you can derive it yourself. Thank you so much! I will be sure to check your videos out for future concepts!
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 brilliant. Please continue to make more such videos. This is how science and math must be seen.
Best explaination ever made for this topic by just one joing lines of a traingle you explained the smallest detail. Thank you very much for this it was so much helpful.
This + thinking gives refreshing perspective on what the heck my lecturer been trying to get to me. It's always the fact that you need to process raw information first, before understanding it normally.
Its been a month since I graduated engineering, and now is the day when I truly understand this algorithm
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!
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 !!!!😢😢😢😢😢😢😢.
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.
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.
Please make more videos! This is an amazing explanation, I love that you're teaching it through using visuals :)
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.
This was mind-blowing to watch. I'm amazed at how you could convey everything so neatly and clearly.
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!
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! :)
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.
Thank you, that was actually the visualization I needed to see to finally understand the logic of the Euclidean algorithm!
WOW. You explain stuff in such an intuitive manner
Whaaaaaaaaaaaat?! Wow! thank you so much for this visual example, it's so good and can be configured for an activity on one of my classes!
This is excellent for giving intuition, understanding AND the ability to actually use it, thank you.
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!
This should be first hit for Euclidean algorithm
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
best video on this topic by far
I really like your channel. Your method of exposition is exceptional.
What a beautiful time to be alive.!
Really the best explanation. I wish this channel grows.
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
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 TH-cam videos because you can't fix them! :) Anyway, thanks for pointing that out.
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 :)
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?
this is the best explanation i ever have❣❣
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}
the best explanation, much much easier but the problem is lecture just want exactly like how they explain
Amazing video! I personally think this explanation is much better than the ones shown on AwesomeMath L4
You are an inspirational teacher !
Such a good teacher! Seriously!
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.
Nice, keep up the good work, hope this channel be great soon, Great explanation and even way to visual it
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!
Thanks for your explanation! Just a quick correction, in your example, the number of dots is 57 instead of 54. gcd(21, 57) = 3 is still true tho.
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.
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).
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.
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?
Underrated video. Thanks a lot!
Thanks! That's just the right type of video I was looking for. Keep up with the good work!
Perfect Explanation, Thank you!
honestly, this was so cool
Excellent video.
Thank you so much for making us think
Way to teach.❤
Very helpful video! thanks!
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 TH-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
Excellent explanation. Thanks!
Thank you very much ❤❤❤
really love it wish that you make more videos
SO UNDERRATED
you are a legend
Absolutely amazing😍
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 !
Amazing!
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
Great stuff. However, it would have been useful to show an example where there are no common factors except for 1.
Awesome, thanks a lot!
perfecto !!!
Thanks.
Amazing
our explanations are similar except I cut the box Into Identical sections
Prayers ....
I finally get it!
Thanks
Thank you! This was really helpful :))
Rather than the division algorithm you might want to introduce the modular algorithm.
love it;❤
Love you
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!
you are great. i love you
damnnnnn bro!
🤯🤯
❤
This is the first explanation I have seen that describes the deeper understanding. Plus voice is very calm.
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!
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.
I don't understand shit she said . 😅
Williams Ronald White Frank Thomas Anna
Thanks.