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
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!
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.
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.....
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
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.
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
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).
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.
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?
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.
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.
