Can't thank you enough for these videos, my discrete lecturer doesn't use any examples and is terribad. You've helped me pull a B in the course so thankyou!
You are the best man, the best in all youtube that talks about discrete structures/math. All the others are hard to understand to me. You make it so simple.
I see how the proof demonstrated that the gcd(a,b) was a common divisor of b and r, and vise verse, but how does this demonstrate that the gcd(a,b) is the greatest common divisor of b and r? How is this demonstrated by the proof as it is stated? Or how might this be deduced from what was proved? Thank you, Chris
Assume gcd(b,r) is larger than gcd(a,b). By the proof in the video, gcd(b, r) divides a and b. Therefore it is a common factor of a and b which is larger than gcd(a, b), contradiction. By the video also, gcd(a, b) divides b and r. In other words, it is a common factor of b and r. So, gcd(b, r) cannot be smaller than gcd(a, b). Hence gcd(a, b) = gcd (b,r)
What if at the end of the solution both numbers aren't exactly divided by the gcd what do you do? Say for eg I have gcd(105,385) where 105 is a and 385 is b*some other constant q. At the end of this, I get 77 it only exactly divides 385.
77 Isn't the Greatest Common Divisor of 105 and 385. 35 is the GCD - the biggest number that can divide BOTH 105 AND 385, WITHOUT leaving a remainder. You perform the gcd algorithm( a = bq+r ) until you have no remainder (the point where b=1 and r=0), you look at the previous step and the value of b there.
He doesn't say that 6*6 = 30, he says that it's obvious that 30 and 6 are both divisible by 6 and that its obviously the biggest number which they share as a divisor.
i dont understand your explaning even though i dont need this stuff right now just doing my hard math since im only in 5th grade and they didnt teach it to my class yet though i know but when my teacher explins this i didnt really get it so i have to search on youtube
Hey hope you are doing alright just I wanna say that GOD loved the world so much he sent his only begotten son Jesus to die a brutal death for us so that we can have eternal life and we can all accept this amazing gift this by simply trusting in Jesus, confessing that GOD raised him from the dead, turning away from your sins and forming a relationship with GOD..
![[Discrete Mathematics] Euclidean Algorithm and GCDs Examples](http://i.ytimg.com/vi/e_Kl5kvRuJs/mqdefault.jpg)
![[Discrete Mathematics] Euclidean Algorithm and GCDs Examples](/img/tr.png)
I‘d say that this guy makes the best videos about Discrete Structures
Hey man. This was the most clear and well explained videos I could find on this topic. Thank you.
Can't thank you enough for these videos, my discrete lecturer doesn't use any examples and is terribad. You've helped me pull a B in the course so thankyou!
pulled an all nighter watching your videos for my exam today. gonna kill it.
Can we have an update?
Howd it go ?
This is me right now. ;_;
You failed the exam, didn't you?
I sure am going to @@noj1yt
You are saving my grade right now because you make a lot more sense then my prof
Hey I know it's been half a decade, but I just came across your comment and was curious. How'd the rest of your class go?
perfect explanation, no weird accent, perfectly audible, readable, understandable.
You are the best man, the best in all youtube that talks about discrete structures/math. All the others are hard to understand to me. You make it so simple.
I have to say that this is the coolest thing I've seen in math for a long time. Such a cool trick!
thx man. your video saved my skin again
Excellent explanation! Understandable for someone who has ZERO math background!
Hey man. This was the most clear and well explained videos I could find on this topic. Thank you.
Euclidean algorithm? More like "Amazing explanation, that's the best of 'em!" Thanks so much for making this video and explaining things so clearly. 👍
Still saving lives 9 years later
It seems like Trev proved the forward and backward on the iff, but only proved that they're common divisors... not ~ greatest ~ common divisors.
the gcd is actually 218
Yes, he didn't prove that it's the greatest common divisor, only that d is a common divisor
Thanks a lot for making these videos they really help out.
I see how the proof demonstrated that the gcd(a,b) was a common divisor of b and r, and vise verse, but how does this demonstrate that the gcd(a,b) is the greatest common divisor of b and r? How is this demonstrated by the proof as it is stated? Or how might this be deduced from what was proved? Thank you, Chris
Assume gcd(b,r) is larger than gcd(a,b). By the proof in the video, gcd(b, r) divides a and b. Therefore it is a common factor of a and b which is larger than gcd(a, b), contradiction.
By the video also, gcd(a, b) divides b and r. In other words, it is a common factor of b and r. So, gcd(b, r) cannot be smaller than gcd(a, b).
Hence gcd(a, b) = gcd (b,r)
@@lordspongebobofhousesquare1616 if you have assumed gcd(b,r) greater than gcd(a,b) , then how can you say gcd(b, r) divides a and b ?
Thank goodness I found this before another discrete exam
Thanks. Though This didn’t actually tell me anything I didn’t already read in my material. But the way you explained it help me understand it better.
Well done! finally got the easiest proof.
Thanks for the lovely explanation, but your proof doesn't explain that why it has to be 'greatest'? is can be any common divisor.
Sir your method of teaching is excellent 👍👍👍
thank you very much. you saved my booty with these vids. keep up the great work.
You are owesome 🙏👌🙋you deserve to be million subscriber.
Awesome proof and knowledge. Thank you for the great example.
Thank you!!! I knew there was a better way to find the GCD, my textbook lied to me lol.
Can you make a video on how to find integers k and l using Euclid Theorem? Thanks.
Excellent explanation.
great explanation
Thank you it helps!
If D divides A then shouldn't we write a/d and not the other way round?
i still cant understand the proof of algorithm. can you make some examples that easy to understand? thanks in advance :)
ua-cam.com/video/qym5D5bhoQs/v-deo.html
You are right Tilu.Even if you understand the procedure for finding THE GCD. the proof is still elusive.
Can you touch on the Corollary - Elementary Number Theory
Nice vid man
does these videos cover the entire syllabus of a course in discrethe mathematics?
thanks for the help!
You can go lower right? 30 = 6*5, or did I miss something?
Yeah, but then you get 30=6*5+0, and the gcd of 6 and 0 is 6.
Best explanation
Thank you. you saved me
This is awesome!
What if the second number is larger than the first? How should I solve that?
I think you could just switch the order of the two numbers and proceed with the same sequence of steps.
10 minute video on YT > multimillionaire textbook authors, tenured professors lol
thank you
Was it not known before naming the process as Euclidean algorithm ?.
Thanks alot!
How can u claim that d divides b and r and also d is gcd?
Which program do you use as pencil?
What if for d | a - qb, d = 3, a = 6, q = 2 and b = 3. That would result in 3 | 6 - (3 x 2) = 3 | 0. How's that valid?
Any number can divide 0 evenly
What if at the end of the solution both numbers aren't exactly divided by the gcd what do you do? Say for eg I have gcd(105,385) where 105 is a and 385 is b*some other constant q. At the end of this, I get 77 it only exactly divides 385.
Then you have your GCD!
So it doesn't matter if i get a remainder?
77 Isn't the Greatest Common Divisor of 105 and 385.
35 is the GCD - the biggest number that can divide BOTH 105 AND 385, WITHOUT leaving a remainder.
You perform the gcd algorithm( a = bq+r ) until you have no remainder (the point where b=1 and r=0), you look at the previous step and the value of b there.
Shouldn't it be a/d instead of d/a as d is the divisor and not the dividend.
i think you should proof that d is the greatest common divisor you just proved that d is a common divisor not the greatest
assume e>d --> e|r and e|b then e|(bq+r) so e|a there is a contradiction thus d is the greatest cd
prove d= as+bt
6*6 is 36 not 30, i think you messed up at 3:20...
xD
He doesn't say that 6*6 = 30, he says that it's obvious that 30 and 6 are both divisible by 6 and that its obviously the biggest number which they share as a divisor.
@@DerPanda93
3 divides 6 and 30
Respect ya
What if you get something like "Find gcd(10^20, 6^30)"
It seems your proof shows that d is a common factor but not the greatest common factor. Am I wrong?
why b=bq+r
thanksssssssssss
Davis Ruth Davis Joseph Davis Ruth
Ok ok… um what did he say srry I’m too young to understand this U-U
You realize ur a prophet in the discrete maths world right ?
i dont understand your explaning even though i dont need this stuff right now just doing my hard math since im only in 5th grade and they didnt teach it to my class yet though i know but when my teacher explins this i didnt really get it so i have to search on youtube
wtf
Hey hope you are doing alright just I wanna say that
GOD loved the world so much he sent his only begotten
son Jesus to die a brutal death for us so that we can have eternal life and we can all accept this amazing gift this by simply trusting in Jesus, confessing that GOD raised him from the dead, turning away from your sins and forming a relationship with GOD..