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
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
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!
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.
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).
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
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.....
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?
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.
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
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!
The theorem proven at the end was what I was looking for, thank you!!
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 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
I rarely leave comments but I just wanted to tell you that this video is full and brilliant.
Thank you for an excellent proof of the Euclidean algorithm. Exceptionally clear and thorough.
Very nice and clear explanation. Thanks. Would love to see more videos from you
Thank you so much for your videos. Your explanations are so clear and concise - excellent maths brain!
I was struggling understanding the proof and I finally got the intuition thanks to this video.
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
Outline:
Algorithm (0:40)
Example - Find gcd of 34 and 55 (2:29)
Why it Works (3:58)
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
Well organized proof. QED. Carl Gauss: Number theory is the Queen of Mathematics.
What about the king?
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!
I watched on 4 different channels and i understand that only you did. So thank u.
Very well explained, thank you!
You made this algorithm very easy to understand, thank you very much for this great video
Great explanation and helps a lot with my study!! Thank you so much for sharing this.
Such a great teacher you are! Thanks!
If you mention your other video while explaining, please leave a link.
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.
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.
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.
Pls make a video on hcf and lcm of fractions with their proof
Thank you so much for making this video
great proof thank you so much for this!
very good proof explanation
Thank you so much, you proof the theorem clearly.
One of the best tutorial I have ever found 🔥
i did not understand the last conclusion , can any one explain it to me from 08:13
talk about perfection!
Which country are you from ma'am ?
I want to meet you, you are such a wonderful teacher.
wow, very intuitive, thanks
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!
nicely explained and in depth.Thank you!
To understand completely, why gcd(a,b)=gcd(b,r) , first try to understand why gcd(a,b) !=gcd(a,r).
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.
Excellent explanation, understood clearly 😃
Very helpful.
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?
Hopefully great video for the proof of this algorithm
Thanks very much for making this easy to understand.
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.
very nicely done👍
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 !
Well explained . Thanks a lot !
Best explanation ❤
short and informative.. perfect.
Thank you so much, that helps!!
3:30 you made the fibonacci sequence!!
Wow mind blown
Thank you sir :) I have studied many topics of Vidya Guru channel as well. They also use updated exam relevant content.
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.....
best explanation i've found so far, but brain still kinda fried lol
Wonderful
Thank you!
Finally i understood this..... thanx a lot😁
Very well done presentation! You should be really popular!
Very good
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.
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.
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
thank you so much for doing this🎉
Thank you so much maam
a great video, thank you ! (LIKED IT AND SUBSCRIBED)
Thank you
3:30 i think gcd(55,34) is 2 as ri here is 2
beautiful. thank you.
Thank you so much.
You got my sub 👍 and a thanks.
Thanks 🙏 for helping me
Thank you so much!
Thanks a lot this really helped! :)
Should the last line in the example not be "2=1(2) +0" ?
Hans van den Bogert
Yes definately
thank you. very helpful
Thank you very much
Thank u sooo much maam👍
thanks
absolutely amazing thank you so much ! you are awsome.
Thanks a lot
Excellent.
Thank you so much :)
Thanks a ton!
Good! Thank you
Thank u 😊
Neat.
THIS IS SO TO THE POINT .............. HATSsssOFF
日本語の教科書よりわかりやすい
Great job, it's really clear, thanks for that :) Jesus bless ❤
ALL I CAME FOR WAS IN 6.26 AND DIDN'T UNDERSTAND IT .... DAMM IT
kjb
1 min into the vid and im already stuck :(
sesxx
Thank you
Thank you!
Thank you
Thank you