I explain the Euclidean Algorithm, give an example, and then show why the algorithm works. Outline: Algorithm (0:40) Example - Find gcd of 34 and 55 (2:29) Why it Works (3:58)
you just something I've used 20 minutes struggling to even begin to understand, and explained it in such a simple way in like 5 minutes. Wish more math teachers were like you
Really this video has helped me a lot......never wondered such beautiful stuff could be arrived by just using these simple steps........school teachers never make us fall in love with maths by providing such beautiful proofs.... Thanks a lot mam..... ❤️🧡💛💚💙💜🤎🤍_from india.....
great explanation thank you! it would be great if you can find some time to make more videos like this :) but thanks a lot for the ones that you already made!
4:31 actually the theorem was proved by using the Euclidean Algorithm, while Euclidean Algorithm is proved using strong induction over the variable a here
Nice way to explain. May Allah bless u a sound health. Also voice is also great. Which is easily understandable.. Keep students make there issues clarify on priority. Also make more math videos on m phil topics plz.
this is really well done! please keep making videos of more math proofs...especially on topics like calculus...please..this video is very clear to understand...and thank you for this video
Wow you have explained it very nicely, but your proof doesn't still explains that why the common divisor would be the "greatest" and not any common divisor? How to prove that d=e?
The proof shows that the set of numbers of the form d (that divide a, b, and r) and the set of numbers of the form e (that divide a, b, and r) exactly match. These are finite sets, and they have a largest element, so those largest elements must match.
Hi there, I liked your explanation here. Very concise. However, I am missing a piece of the puzzle. So far, we proved 1) if d is a factor a and b, then d divides r 2) if d is a factor of b and r, then d divides a But how do we imply from these 2 statements that d is the gcd? i.e. we only proved that d is a factor of the 3 items, but not the greatest divisor? Thanks!
The set of common divisors between a,b is identical to the set of common divisors of b,r The greatest common divisor is simply the greatest number of the set of common divisors. If the two sets are the same, the greatest member of the set must also be the same for both. So the gcd is the same for both pairs.
@@thechaoslp2047 I think this is what I was missing. I was too hung up on the fact that we only got common divisors for both sets, and did not prove that the fact that the common divisors are the greatest common divisor.
Anytime you have d "dividing" a number (i.e. d divides b), then it divides a multiple of that number (so d divides bq). For example, if 6 divides 12, then 6 divides 24, and 36, and 48, etc. So if d|b, then d|bq. Furthermore, if d divides two different numbers, a and bq, then it divides their sum or difference, since if it's a factor of both, you can "factor it out" of the expression. So, if d|a and d|b, then d also divides bq, and therefore it divides a - bq.
It's clearer if we write it like this: Forward: (d|a AND d|b) -> (d|r AND d|b). Note, 'd' is any common divisor of 'a' and 'b'. Backward: (e|b AND e|r) -> (e|a AND e|b). Here, 'e' is any common divisor of 'b' and 'r'. So, any common divisor 'a' and 'b' is a common divisor of 'r' and 'b'. Also, any common divisor of 'b' and 'r' is a common divisor of 'a' and 'b'. Therefore, (a, b) and (b, r) share the same set of common divisors. Thus, the gcd(a, b) = gcd(b, r) as needed.
@@abuabdullah9878 Dude, how can you tell that the shared common divisor is the gcd? I did not quite get your last sentence and the last step in the video.
@@mountainsunset816 the way I've figured it, is we now know that the 2 sets are identical. So d and e and f and g and so on for however many iterations, all are common divisors in an identical set. So d for example could be any divisor in the set and e could also be any divisor and so on. Say for e.g you do a lot of iterations and get an answer of 1233 = 3(411) +0 You have now reached the point where there is no remainder left. We now know that any common divisor of 1233 and 411 is also any common divisor of the original a and b (in this case a=7398 and b=2877) So if we want to know the greatest or largest common divisor of 7398 and 2877, then simply find the gcf of 1233 and 411. Well, there is no remainder and 411×3 = 1233 as figured out by the iterations. So 411 must be the gcf(1233,411). Thus it is the gcf(7398,2877). Please feel free to correct me if I'm wrong, I just thought I'd learn some uni maths in lockdown before I start uni, so I could be completely and utterly incorrect
@@@adam-jm1gq @Mountain Sunset: You're both on the right track. As Abu indicated, the shown steps demonstrate that (a, b) and (b, r) share the same set of common divisors -- and so do any of the (a,b,r)-type combinations throughout the sequence of steps. So (b, r) and (r, r_1) share the same set of common factors, as do (r,r_1) and (r_1,r_2)...all the way down to (r_i-1,r_i) sharing the same set of common factors as (r_i,0). But the greatest common factor of r_i and 0 is simply r_i! So you can think of this value propagating all the way back up through the sequence, since any LARGER divisor common to (a,b) would also be common to (b,r), which would be common to (r, r_1), ...all the way down to (r_i,0).
If d is a divisor of b, then it would have to be a divisor of any multiple of b. And bq is a multiple of b. For example, if 6 divides 12 (letting d = 6 and b = 12), then 6 divides 12(3) (letting q = 3). More generally, once you know 6 "goes into" 12, you know that 6 "goes into" any multiple of 12. Once you know d "goes into" b, you know that d "goes into" b times any other whole number, so it "goes into" b times q.
I mean tho its fairly obvious that a multiple subtracted from a greater multiple is still a multiple, don't u have to prove that a-bq is also divisible by d?
This is the best video I could find on the internet that explains the Euclidean Algorithm so concisely and comprehensibly. Thanks a bunch!
Y'r right !
Ma'am, this has to be the best mathematics video on UA-cam that I've seen. So concise and immensely explanatory!!! Thank you very much! Subscribed!
you just something I've used 20 minutes struggling to even begin to understand, and explained it in such a simple way in like 5 minutes. Wish more math teachers were like you
The theorem proven at the end was what I was looking for, thank you!!
I had been trying to decipher someone else's post on this for hours on end with no luck. Watching this video completely cleared it up for me! Thanks!
This is so well done. Why isn't this the top result when I search on google. Literally so much clearer than the textbook!!!
I rarely leave comments but I just wanted to tell you that this video is full and brilliant.
I am actually in 10th standard and I was wondering why does the Euclid's Algorithm works ? And here is the answer thank you ma'am
Same here bro
Thank you for an excellent proof of the Euclidean algorithm. Exceptionally clear and thorough.
Thank you so much for your videos. Your explanations are so clear and concise - excellent maths brain!
Very nice and clear explanation. Thanks. Would love to see more videos from you
I was struggling understanding the proof and I finally got the intuition thanks to this video.
I watched on 4 different channels and i understand that only you did. So thank u.
Very well explained, thank you!
Well organized proof. QED. Carl Gauss: Number theory is the Queen of Mathematics.
What about the king?
Great explanation and helps a lot with my study!! Thank you so much for sharing this.
You made this algorithm very easy to understand, thank you very much for this great video
great proof thank you so much for this!
Thank you so much for making this video
One of the best tutorial I have ever found 🔥
Thank you so much, you proof the theorem clearly.
It always amaze me to think that ones upon a time someone thought of this.
Yeah, same for me. Considering how much humanity has grown in the last century, we tend to think that the humans before were apes
wow, very intuitive, thanks
Such a great teacher you are! Thanks!
Really this video has helped me a lot......never wondered such beautiful stuff could be arrived by just using these simple steps........school teachers never make us fall in love with maths by providing such beautiful proofs....
Thanks a lot mam.....
❤️🧡💛💚💙💜🤎🤍_from india.....
Thank you sir :) I have studied many topics of Vidya Guru channel as well. They also use updated exam relevant content.
great explanation thank you! it would be great if you can find some time to make more videos like this :) but thanks a lot for the ones that you already made!
4:31 actually the theorem was proved by using the Euclidean Algorithm, while Euclidean Algorithm is proved using strong induction over the variable a here
talk about perfection!
very good proof explanation
Thanks very much for making this easy to understand.
Very helpful.
Thank you so much, that helps!!
Thank you so much maam
short and informative.. perfect.
Hopefully great video for the proof of this algorithm
nicely explained and in depth.Thank you!
Excellent explanation, understood clearly 😃
Very good
Well explained . Thanks a lot !
Outline:
Algorithm (0:40)
Example - Find gcd of 34 and 55 (2:29)
Why it Works (3:58)
Finally i understood this..... thanx a lot😁
Pls make a video on hcf and lcm of fractions with their proof
Wonderful
Thank you!
very nicely done👍
Thank you
3:30 you made the fibonacci sequence!!
Wow mind blown
At 3:44, I think the last equation should be 2 = 1*(2) + 0 instead of 2 = 2*(1) + 0
+Peter Ren That's right.
Nice way to explain. May Allah bless u a sound health.
Also voice is also great. Which is easily understandable.. Keep students make there issues clarify on priority.
Also make more math videos on m phil topics plz.
What a wonderful Video. I applaud you. I suggest you include a "Thanks you" at the end, gives the video closure when playing full screen.
beautiful. thank you.
a great video, thank you ! (LIKED IT AND SUBSCRIBED)
thank you so much for doing this🎉
Thanks 🙏 for helping me
absolutely amazing thank you so much ! you are awsome.
You got my sub 👍 and a thanks.
Thank you so much.
Excellent.
this is really well done! please keep making videos of more math proofs...especially on topics like calculus...please..this video is very clear to understand...and thank you for this video
Good to see there are people like you actually interested and not just blindly applying formulas.
you shut ur mouth up !
If you mention your other video while explaining, please leave a link.
Thanks a lot
thanks
best explanation i've found so far, but brain still kinda fried lol
Wow you have explained it very nicely, but your proof doesn't still explains that why the common divisor would be the "greatest" and not any common divisor? How to prove that d=e?
The proof shows that the set of numbers of the form d (that divide a, b, and r) and the set of numbers of the form e (that divide a, b, and r) exactly match. These are finite sets, and they have a largest element, so those largest elements must match.
Thank you very much
Thank you so much!
thank you. very helpful
Thank u sooo much maam👍
Which country are you from ma'am ?
I want to meet you, you are such a wonderful teacher.
i did not understand the last conclusion , can any one explain it to me from 08:13
Very well done presentation! You should be really popular!
Thanks a ton!
Thank you so much :)
To understand completely, why gcd(a,b)=gcd(b,r) , first try to understand why gcd(a,b) !=gcd(a,r).
Good! Thank you
Thanks a lot this really helped! :)
Hi there, I liked your explanation here. Very concise.
However, I am missing a piece of the puzzle. So far, we proved 1) if d is a factor a and b, then d divides r
2) if d is a factor of b and r, then d divides a
But how do we imply from these 2 statements that d is the gcd? i.e. we only proved that d is a factor of the 3 items, but not the greatest divisor?
Thanks!
Exactly, I am also confused about this.
Just got it. Since d can be any factor, so it can also be the greatest common divisor.
I think it helps to understand that it works for ANY divisor.
The set of common divisors between a,b is identical to the set of common divisors of b,r
The greatest common divisor is simply the greatest number of the set of common divisors.
If the two sets are the same, the greatest member of the set must also be the same for both.
So the gcd is the same for both pairs.
@@thechaoslp2047 I think this is what I was missing. I was too hung up on the fact that we only got common divisors for both sets, and did not prove that the fact that the common divisors are the greatest common divisor.
Thank u 😊
THIS IS SO TO THE POINT .............. HATSsssOFF
I dont understood one point that is, how d|a, d|b implies that d|a-bq. Please any buddy explain me.
Anytime you have d "dividing" a number (i.e. d divides b), then it divides a multiple of that number (so d divides bq). For example, if 6 divides 12, then 6 divides 24, and 36, and 48, etc. So if d|b, then d|bq. Furthermore, if d divides two different numbers, a and bq, then it divides their sum or difference, since if it's a factor of both, you can "factor it out" of the expression. So, if d|a and d|b, then d also divides bq, and therefore it divides a - bq.
Thank you buddy. Nice explanation.
@@lbmath5441
i lost you after you said e | a at 8:04. how did you get to the 'iff' statement ?
It's clearer if we write it like this:
Forward: (d|a AND d|b) -> (d|r AND d|b). Note, 'd' is any common divisor of 'a' and 'b'.
Backward: (e|b AND e|r) -> (e|a AND e|b). Here, 'e' is any common divisor of 'b' and 'r'.
So, any common divisor 'a' and 'b' is a common divisor of 'r' and 'b'. Also, any common divisor of 'b' and 'r' is a common divisor of 'a' and 'b'. Therefore, (a, b) and (b, r) share the same set of common divisors. Thus, the gcd(a, b) = gcd(b, r) as needed.
@@abuabdullah9878 Dude, how can you tell that the shared common divisor is the gcd? I did not quite get your last sentence and the last step in the video.
@@mountainsunset816 the way I've figured it, is we now know that the 2 sets are identical. So d and e and f and g and so on for however many iterations, all are common divisors in an identical set. So d for example could be any divisor in the set and e could also be any divisor and so on.
Say for e.g you do a lot of iterations and get an answer of 1233 = 3(411) +0
You have now reached the point where there is no remainder left.
We now know that any common divisor of 1233 and 411 is also any common divisor of the original a and b (in this case a=7398 and b=2877)
So if we want to know the greatest or largest common divisor of 7398 and 2877, then simply find the gcf of 1233 and 411. Well, there is no remainder and 411×3 = 1233 as figured out by the iterations. So 411 must be the gcf(1233,411). Thus it is the gcf(7398,2877). Please feel free to correct me if I'm wrong, I just thought I'd learn some uni maths in lockdown before I start uni, so I could be completely and utterly incorrect
@@@adam-jm1gq @Mountain Sunset: You're both on the right track. As Abu indicated, the shown steps demonstrate that (a, b) and (b, r) share the same set of common divisors -- and so do any of the (a,b,r)-type combinations throughout the sequence of steps. So (b, r) and (r, r_1) share the same set of common factors, as do (r,r_1) and (r_1,r_2)...all the way down to (r_i-1,r_i) sharing the same set of common factors as (r_i,0). But the greatest common factor of r_i and 0 is simply r_i! So you can think of this value propagating all the way back up through the sequence, since any LARGER divisor common to (a,b) would also be common to (b,r), which would be common to (r, r_1), ...all the way down to (r_i,0).
@@andrewkarem5874 Oh, you made it so clear! Thank you!
Neat.
Great job, it's really clear, thanks for that :) Jesus bless ❤
So the common divisors are the same, but why greatest? Is this some anecdote that has been found over centuries or is there proof available for it?
3:30 i think gcd(55,34) is 2 as ri here is 2
Wait, pause. How does d being a divisor of b suddenly make d being a divisor of bq? How did you reach that conclusion?
If d is a divisor of b, then it would have to be a divisor of any multiple of b. And bq is a multiple of b. For example, if 6 divides 12 (letting d = 6 and b = 12), then 6 divides 12(3) (letting q = 3). More generally, once you know 6 "goes into" 12, you know that 6 "goes into" any multiple of 12. Once you know d "goes into" b, you know that d "goes into" b times any other whole number, so it "goes into" b times q.
Should the last line in the example not be "2=1(2) +0" ?
Hans van den Bogert
Yes definately
I mean tho its fairly obvious that a multiple subtracted from a greater multiple is still a multiple, don't u have to prove that a-bq is also divisible by d?
no, because (a-bq)/d => a/d - (b/d)q, and that's an integer since a/d and b/d are integers, meaning it is divisible.
日本語の教科書よりわかりやすい
ALL I CAME FOR WAS IN 6.26 AND DIDN'T UNDERSTAND IT .... DAMM IT
1 min into the vid and im already stuck :(
kjb
sesxx
Thank you
Thank you!
Thank you
Thank you