Best explanation of the Euclid algorithm I found on KZbin, gives me intuition instead of just describing how to compute it or proving it.
@ProofofConceptMath3 жыл бұрын
Thank you!
@jaideepshekhar4621 Жыл бұрын
Same. :)
@gsriram183024 күн бұрын
This is brilliant. Please continue to make more such videos. This is how science and math must be seen.
@marklord761413 күн бұрын
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.
@stefanienix74472 жыл бұрын
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!
@gravity6316Ай бұрын
WOW. You explain stuff in such an intuitive manner
@fd932 жыл бұрын
Please make more videos! This is an amazing explanation, I love that you're teaching it through using visuals :)
@akshat.jaiswal3 жыл бұрын
Thanks! That's just the right type of video I was looking for. Keep up with the good work!
@navauchihaАй бұрын
This should be first hit for Euclidean algorithm
@valeryjuli2 жыл бұрын
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!
@manarsalem16852 ай бұрын
This was mind-blowing to watch. I'm amazed at how you could convey everything so neatly and clearly.
@Frownlandia2 жыл бұрын
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.
@ProofofConceptMath2 жыл бұрын
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.
@akshatkalra41142 жыл бұрын
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.
@timetravellingblockhead2122 Жыл бұрын
This is excellent for giving intuition, understanding AND the ability to actually use it, thank you.
@kashikakhera949210 ай бұрын
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
@pectenmaximus2312 жыл бұрын
I really like your channel. Your method of exposition is exceptional.
@henrynwosu62777 ай бұрын
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 !!!!😢😢😢😢😢😢😢.
@jathebest2835 Жыл бұрын
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.!
@hidrogenhelium78492 жыл бұрын
Nice, keep up the good work, hope this channel be great soon, Great explanation and even way to visual it
@jaideepshekhar4621 Жыл бұрын
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! :)
@luciepopova5907 Жыл бұрын
Thank you, that was actually the visualization I needed to see to finally understand the logic of the Euclidean algorithm!
@ramkoduri99072 жыл бұрын
Really the best explanation. I wish this channel grows.
@lolkk97472 жыл бұрын
Such a good teacher! Seriously!
@carlosraventosprieto20658 ай бұрын
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 :)
@bartomiejpotaman69736 ай бұрын
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!
@caiofernandoАй бұрын
Excellent video.
@kal8266 Жыл бұрын
Perfect Explanation, Thank you!
@stevecreighton33522 жыл бұрын
You are an inspirational teacher !
@yaronyahav65611 ай бұрын
Excellent explanation. Thanks!
@kwazar374 Жыл бұрын
Underrated video. Thanks a lot!
@TheWesternPrince6 ай бұрын
Amazing video! I personally think this explanation is much better than the ones shown on AwesomeMath L4
@vadrif-draco Жыл бұрын
This is pretty visual and intuitive, thank you.
@vadrif-draco Жыл бұрын
Bruh I was already impressed but then you went with the speed-up portion and took it to a new level of impressive!
@brunilda Жыл бұрын
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.
@nourkhamis39312 жыл бұрын
really love it wish that you make more videos
@mdaalishanraza39282 жыл бұрын
Very helpful video! thanks!
@Mark-nm9sm9 ай бұрын
Thank you so much for making us think
@kiralight6825 Жыл бұрын
Amazing!
@shubhankarkarn37472 жыл бұрын
Absolutely amazing😍
@ianweckhorst320011 ай бұрын
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
@ch1llp1ll432 жыл бұрын
Thank you! This was really helpful :))
@DL-re2mv Жыл бұрын
best video on this topic by far
@ShivamKumar-kd1ww2 жыл бұрын
What a beautiful time to be alive.!
@Jbortoletto3 жыл бұрын
Awesome, thanks a lot!
@viniciusfriasaleite80162 жыл бұрын
Looks like the pile B has 57 stones on the image... but that doesn't change the explanation, it's very good
@ProofofConceptMath2 жыл бұрын
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 KZbin videos because you can't fix them! :) Anyway, thanks for pointing that out.
@a-n.o.n-y.m.o.u.s2 жыл бұрын
Way to teach.❤
@naruhitoabiku94517 ай бұрын
you are a legend
@MrJHinism5 күн бұрын
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.
@locopenguin61615 ай бұрын
Amazing
@wowashlam2 жыл бұрын
you are great. i love you
@md.arifulislamroni29462 ай бұрын
love it;❤
@AbjSir2 ай бұрын
Thanks.
@kaleabtadewos93442 жыл бұрын
perfecto !!!
@estrom10011 ай бұрын
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.)
@alex_turing Жыл бұрын
Thanks
@vickyli6610 ай бұрын
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?
@trampflips101 Жыл бұрын
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?
@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!
@SirTravelMuffin2 жыл бұрын
I finally get it!
@scollyer.tuition2 жыл бұрын
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}
@factopedia105412 күн бұрын
Love you
@compucademy3 жыл бұрын
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?
@ProofofConceptMath3 жыл бұрын
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 KZbin 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.
@anothermoth2 жыл бұрын
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.
@jaideepshekhar4621 Жыл бұрын
Well, we ARE just "confirming" the gcd when we compute it. It already exists!
@brunilda11 ай бұрын
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
@marcvanleeuwen598611 ай бұрын
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.
@sahilsharmahere2 жыл бұрын
Euclid from the heavens: Ohh mistress with a beautiful soul, may god blesseth thee.
@goldenboy76979 ай бұрын
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.
@lp99312 жыл бұрын
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?
@lp99312 жыл бұрын
Sorry didnt watch till end of vid where you explain this. My bad
@Viral_vittles Жыл бұрын
Prayers ....
@cellmaker16 ай бұрын
Great stuff. However, it would have been useful to show an example where there are no common factors except for 1.
@pedrorivera44052 жыл бұрын
Basic question: What is the operator / symbol "|" displayed in the proof at 13:20?
@pedrorivera44052 жыл бұрын
Ok found the answer later in the video. a | b means a is an integer divider of b.
@ProofofConceptMath2 жыл бұрын
@@pedrorivera4405 You are correct! (I think the timestamp is closer to the 7-8 minute mark?)
@anabhayansp3696 Жыл бұрын
@@pedrorivera4405 I had the same doubt, thank you !
@timothylei75582 жыл бұрын
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).
@ahmadag1820Ай бұрын
our explanations are similar except I cut the box Into Identical sections
@klevisimeri6076 ай бұрын
❤
@klevisimeri6076 ай бұрын
This is the first explanation I have seen that describes the deeper understanding. Plus voice is very calm.
@hannesstark50243 жыл бұрын
I think you have a typo: the 5 in the factorization of b should have exponent 3 not 2 :D
@hannesstark50243 жыл бұрын
And lovely video!
@ProofofConceptMath3 жыл бұрын
@@hannesstark5024 Thank you! I'm sorry about the typo -- you are right about that!
@robinpettit78272 жыл бұрын
Rather than the division algorithm you might want to introduce the modular algorithm.
@BestHolkin2 жыл бұрын
I see the proof for a common divisor, but where is the proof it is a largest possible common divisor?
@jaideepshekhar4621 Жыл бұрын
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.
@BestHolkin Жыл бұрын
@@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?
@harshitpandey32455 ай бұрын
@@BestHolkin Exactly the same thought! Glad someone said it!
@steveglemaud34595 ай бұрын
I don't understand shit she said . 😅
@cursedswordsman2 жыл бұрын
Makes no sense. Not clear at all why there aren't two groups of 3 remaining in the end, for example.
@jaideepshekhar4621 Жыл бұрын
Why would there be 2 groups of 3 in the end? The pattern is still there, and can be removed.