Euclidean Algorithm (Proof)

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)

[@praveenanookala4457]

Ma'am, this has to be the best mathematics video on KZbin that I've seen. So concise and immensely explanatory!!! Thank you very much! Subscribed!

[@glitch3dout]

This is the best video I could find on the internet that explains the Euclidean Algorithm so concisely and comprehensibly. Thanks a bunch!

[@manishsahamanishsaha1268]

Y'r right !

[@episkefilm8153]

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

[@octavios8081]

The theorem proven at the end was what I was looking for, thank you!!

[@Pandafist3000]

Thank you for an excellent proof of the Euclidean algorithm. Exceptionally clear and thorough.

[@peteryongzhong5516]

This is so well done. Why isn't this the top result when I search on google. Literally so much clearer than the textbook!!!

[@fixer2508]

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!

[@shauryanagpal1848]

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

[@user-qd4dg3xv3l]

Same here bro

[@hannahpatel7197]

Thank you so much for your videos. Your explanations are so clear and concise - excellent maths brain!

[@tiandao1chouqin]

Very nice and clear explanation. Thanks. Would love to see more videos from you

[@Andrey-ny2dv]

I rarely leave comments but I just wanted to tell you that this video is full and brilliant.

[@lucianocao8787]

I was struggling understanding the proof and I finally got the intuition thanks to this video.

[@gonzalochristobal]

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!

[@davidemasi__]

You made this algorithm very easy to understand, thank you very much for this great video

[@greyshinobi69]

nicely explained and in depth.Thank you!

[@naif277]

Very well explained, thank you!

[@kwokpinglau2400]

Thank you so much, you proof the theorem clearly.

[@mysia8437]

I watched on 4 different channels and i understand that only you did. So thank u.

[@MarziyeFatemi-xg2ty]

Such a great teacher you are! Thanks!

[@raginibhayana8305]

Thank you so much for making this video

[@valeriereid2337]

Thanks very much for making this easy to understand.

[@abd-elrahmanmohamed9839]

Well explained . Thanks a lot !

[@rajendramisir3530]

Well organized proof. QED. Carl Gauss: Number theory is the Queen of Mathematics.

[@kunalsinghgusain2070]

What about the king?

[@adityakrishna11]

great proof thank you so much for this!

[@michaelbachmann457]

very good proof explanation

[@m_sh2240]

thank you so much for doing this🎉

[@RoyalGun-9mm]

short and informative.. perfect.

[@srikantht2403]

Thank you

[@SathvickSatish]

Very well done presentation! You should be really popular!

[@seal0118]

wow, very intuitive, thanks

[@ziedbrahmi4812]

a great video, thank you ! (LIKED IT AND SUBSCRIBED)

[@rishabhpandey3822]

very nicely done👍

[@josephlai7737]

Thank you so much!

[@user-ye7yu2zc4t]

One of the best tutorial I have ever found 🔥

[@silicon9794]

Excellent explanation, understood clearly 😃

[@yeah5037]

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

[@edisonyin9711]

Thank you so much, that helps!!

[@ruthwik8772]

Hopefully great video for the proof of this algorithm

[@aksenchukaleksandr3273]

thank you. very helpful

[@TamNguyen-yk9mn]

It always amaze me to think that ones upon a time someone thought of this.

[@cubingtubing8172]

Yeah, same for me. Considering how much humanity has grown in the last century, we tend to think that the humans before were apes

[@trendytrenessh462]

Thanks a lot this really helped! :)

[@DEEPAKKUMAR-oo1vv]

Thank you so much.

[@krishshah3974]

talk about perfection!

[@pulse5863]

absolutely amazing thank you so much ! you are awsome.

[@abhinavraut3099]

Thank you!

[@math_lover5292]

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.....

[@thechaoslp2047]

beautiful. thank you.

[@AsBi1]

Very helpful.

[@thachpham8597]

Thank you very much

[@aneimabui9718]

Thanks 🙏 for helping me

[@mcat0183]

Thank you so much :)

[@samarthjain5295]

Finally i understood this..... thanx a lot😁

[@HiHi-iu8gf]

best explanation i've found so far, but brain still kinda fried lol

[@edwinshelly993]

Thanks a ton!

[@kunalsinghgusain2070]

You got my sub 👍 and a thanks.

[@mwsedits]

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.

[@gladyouseen8160]

Wonderful

[@mr.shanegao]

Outline: Algorithm (0:40​) Example - Find gcd of 34 and 55 (2:29​) Why it Works (3:58​)

[@calvin2888]

Excellent.

[@mjjeon2292]

If you mention your other video while explaining, please leave a link.

[@ashutoshniwal]

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?

[@willjohnston2959]

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.

[@kunalkashyap9904]

Thank you sir :) I have studied many topics of Vidya Guru channel as well. They also use updated exam relevant content.

[@damandeepsingh8542]

Pls make a video on hcf and lcm of fractions with their proof

[@wpajunior]

Good! Thank you

[@user-ye7yu2zc4t]

Thank you so much maam

[@renjitharejikumar1619]

Thank u sooo much maam👍

[@navyatayi6956]

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

[@marvhartigan3677]

Good to see there are people like you actually interested and not just blindly applying formulas.

[@manishsahamanishsaha1268]

you shut ur mouth up !

[@minatirout3286]

Thanks a lot

[@peterren5409]

At 3:44, I think the last equation should be 2 = 1*(2) + 0 instead of 2 = 2*(1) + 0

[@praveenanookala4457]

+Peter Ren That's right.

[@aryamankarde473]

Which country are you from ma'am ? I want to meet you, you are such a wonderful teacher.

[@damandeepsingh8542]

Very good

[@TheBSpaZZ]

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.

[@zahra-hrm]

Thank u 😊

[@gogoat2412]

3:30 you made the fibonacci sequence!!

[@kushalpawar9571]

Wow mind blown

[@cubingtubing8172]

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?

[@dogamertaydogan2803]

thanks

[@coctaildz5388]

i did not understand the last conclusion , can any one explain it to me from 08:13

[@davidjiang7929]

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!

[@mountainsunset816]

Exactly, I am also confused about this.

[@mountainsunset816]

Just got it. Since d can be any factor, so it can also be the greatest common divisor.

[@kevinmartincossiolozano8245]

I think it helps to understand that it works for ANY divisor.

[@thechaoslp2047]

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.

[@davidjiang7929]

@@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.

[@rameshchandra1696]

Neat.

[@harivatsaparameshwaran4174]

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?

[@biocuts]

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.

[@adityasoni6966]

To understand completely, why gcd(a,b)=gcd(b,r) , first try to understand why gcd(a,b) !=gcd(a,r).

[@champion5545]

Wait, pause. How does d being a divisor of b suddenly make d being a divisor of bq? How did you reach that conclusion?

[@lbmath5441]

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.

[@luciuspertis5672]

THIS IS SO TO THE POINT .............. HATSsssOFF

[@AjayKumar-fb3gx]

i lost you after you said e | a at 8:04. how did you get to the 'iff' statement ?

[@abuabdullah9878]

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.

[@mountainsunset816]

@@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.

[@adam-jm1gq]

@@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

[@andrewkarem5874]

@​@@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).

[@praveenanookala4457]

@@andrewkarem5874 Oh, you made it so clear! Thank you!

[@ankitthakurankit4764]

3:30 i think gcd(55,34) is 2 as ri here is 2

[@legendsplayground7017]

Great job, it's really clear, thanks for that :) Jesus bless ❤

[@abdullaha2108]

I dont understood one point that is, how d|a, d|b implies that d|a-bq. Please any buddy explain me.

[@lbmath5441]

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.

[@abdullaha2108]

Thank you buddy. Nice explanation. @@lbmath5441

[@hansvandenbogert8992]

Should the last line in the example not be "2=1(2) +0" ?

[@simranmulchandani6190]

Hans van den Bogert Yes definately

[@user-ly9vg7bp6l]

日本語の教科書よりわかりやすい

[@user-od2ox5we4b]

ALL I CAME FOR WAS IN 6.26 AND DIDN'T UNDERSTAND IT .... DAMM IT

[@tsunningwah3471]

kjb

[@tsunningwah3471]

sesxx

[@cobi617]

1 min into the vid and im already stuck :(

[@gurumayummadan2646]

Thank you

[@_cytosine]

Thank you!

[@mominmondal1839]

Thank you

[@thetrainoflife8327]

Thank you