The Extended Euclidean algorithm

Поделиться
HTML-код
  • Опубликовано: 23 дек 2024

Комментарии • 220

  • @Adir9
    @Adir9 3 года назад +85

    One of the best explanations. Can't understand why professors have such hard time explaining this, looks so simple here! Thanks a lot.

    • @roobiki4494
      @roobiki4494 Год назад +4

      It would be nice if one day we get to the place where we can celebrate a job well done by one educator, without turning around and shitting on others.

    • @matthewRR03
      @matthewRR03 10 месяцев назад +13

      @@roobiki4494 It's a valid criticism of other educators. Especially considering that the most arrogant and self-righteous ones are always the worst at teaching.

    • @casamigosocean
      @casamigosocean 3 месяца назад

      @@roobiki4494 Keep licking those boots

  • @mg7753
    @mg7753 9 лет назад +178

    Finnaly a good explanation, it's such an easy concept but pretty hard to grasp.

  • @coxandrewj
    @coxandrewj 7 месяцев назад +4

    My lands. I cannot tell you how much time I have spent trying to understand this. This finally, finally, finally, gave me the explanation I needed.

  • @ekstrand26
    @ekstrand26 7 лет назад +19

    Thank you!!!!! Like seriously I have been pulling my hair out trying to understand this. This video actually made it simple and easy to understand. I appreciate what you did, and it made the whole process MUCH easier!!

  • @LastCaressTube
    @LastCaressTube 10 лет назад +24

    Finally a resource that clearly explains what's going on in finding the coefficients of a linear combination. Well done!

  • @illlanoize23
    @illlanoize23 5 лет назад +31

    this isn’t too bad but my teacher wants to make it hard talking at 5000mph smh thank you so much

  • @ionmech
    @ionmech 9 лет назад +3

    Thank you so much, I went into office hours and he seemed to giggle that it did not make sense to me from the one example we worked in class like this, but now I actually get it!

  • @greciangirl75
    @greciangirl75 4 года назад +5

    I was in homework panic and couldn't find a clear explanation on the Extended Euclidean algorithm. This is one of the clearest explanation I had on the topic. Thank you soooo much!

  • @bruhmannen7400
    @bruhmannen7400 3 года назад +3

    Thank you so much for this clear explanation! I have struggled with this algorithm for a while, but you made it so easy to understand!

  • @nathanstewart7792
    @nathanstewart7792 3 года назад +3

    I know this video is from 2014 but I just watched this to make sense of my Discrete Math 2 class and wanted to say thank you for explaining this in such a simple way that makes perfect sense!

  • @MrDivad006
    @MrDivad006 9 лет назад +22

    Excellent explanation, an annotation to the next video at the end would be cool..

  • @aipro8091
    @aipro8091 2 года назад

    omg Tysm, I was studying affine cipher and I didn’t even know number theory existed and this made it so easy to understand and to decrypt affine ciphers. Thank you

  • @theCheug
    @theCheug 8 лет назад

    I have a test tomorrow and this was the only concept that I was just not grasping at all. I now understand it completely. THANK YOU.

    • @sheesh602
      @sheesh602 3 года назад +1

      what did u get on the test 👀

  • @BaD8DeviL
    @BaD8DeviL 9 лет назад +1

    I've read a book many times + I watched many videos..
    but this one was the best explaining this algorithm !!
    thanks a lot ;)

  • @thechesslobster2768
    @thechesslobster2768 4 года назад +1

    Excellent stuff. Between your Multiplicative inverses video, and this one, you've helped me greatly in my Cryptography and Security class.

  • @wyattflippin7610
    @wyattflippin7610 2 года назад

    Thank you so, so much! I had such a hard time grasping the weird arithmetic of these problems until I ran into your video

  • @lindeanchuang8115
    @lindeanchuang8115 2 года назад

    Thanks a million. Your explanation is very clear. It helps me a lot since I will take the midterm exam tomorrow.

  • @SamCarter-p6j
    @SamCarter-p6j Год назад

    You sir are a legend. Made such a complicated topic to me easy.

  • @enya_yurself
    @enya_yurself 3 года назад

    you have no idea how many times i have rewatched this over the past few years
    i keep forgetting :(

  • @Fun_maths
    @Fun_maths 4 года назад

    This helped so much with a problem I needed to tackle in a week and had no idea, thanks so much!

  • @alvinkangoo2857
    @alvinkangoo2857 9 лет назад

    This is the best explanation for the Extended Euclidean Algorithm. Thank you very much for this. Greatly appreciated.

  • @traj250
    @traj250 4 года назад

    Got my discrete math midterm tomorrow, thank you so much, this was super helpful!

  • @yifuxero5408
    @yifuxero5408 Год назад +1

    In the last example he wanted 1180/482. Using a ;pocket calculator this reduces to 241/590. Write out the continued fraction representation = [2, 2, 4, 3, 8] and underneath write the convergents, = [1/2, 2/5, 9/22, 29/ 71, 241/590] For an odd number of convergents (we have 5), the rule is to extract the denominatlor to the left of the rightmost denominator, that is, 71. That's the answer as stated in the lesson.

  • @manaoharsam4211
    @manaoharsam4211 2 года назад

    You did a fantastic job. Good teaching.

  • @DoctorRV
    @DoctorRV 7 лет назад +1

    brilliant explanation..been struggling with this over a day and here we are done in just 12 mins..Thanks a lot!!

  • @killjason1049
    @killjason1049 2 года назад

    best video that efficiently explained the concept, thanks

  • @alexishayes713
    @alexishayes713 6 лет назад

    OMG!!!!! THANK YOU SO MUCH!!! I kept getting stuck on the step towards the last step and you just explained it to where the other vids I watched just neglected to explain that step!

  • @pattanaik1007
    @pattanaik1007 9 лет назад +1

    Well explained. This is by far the simplest I have seen. Thank you for posting. :)

  • @etienne8397
    @etienne8397 2 года назад

    thank you so much for the video. I finally understood this concept now!

  • @ksdivya100
    @ksdivya100 6 лет назад +1

    Thank u so much. I was literally scratching my head learning this in class!

  • @ثانويةخمسنجوم
    @ثانويةخمسنجوم 5 лет назад

    This was the best explanation I receive on this subject.

  • @benballier9580
    @benballier9580 3 года назад

    My professor finished 3 problems and sped through the 2nd portion (the harder part) of these problems in less time than this video is in length.
    Thank you for taking the time to explain it carefully. Better to fully understand one problem than to be confused while the professor rushes through 3.

  • @HouseOrigins
    @HouseOrigins 3 года назад

    School got me all mixed up with complicated terms and you made it so easy to grasp, thank you!.

  • @harrisondong5405
    @harrisondong5405 2 года назад

    good explanation! hope to add more explanation on how to calculate x and y in extended euclidean algorithm

  • @anikatabassum1828
    @anikatabassum1828 Год назад

    Thank you so much. By far the best explanation.

  • @jamiejohnson8144
    @jamiejohnson8144 8 лет назад

    Excellent explanation...great step-by-step instructions!

  • @etelemeszaros4252
    @etelemeszaros4252 7 лет назад

    Thanks man! you helped me a lot! greetings from Hungary!

  • @rafatashraf3669
    @rafatashraf3669 5 лет назад

    Best video on RUclips on this topic . Thanks ....

  • @jerricaflanagan7928
    @jerricaflanagan7928 9 лет назад +1

    This is a much better explanation than my teacher. Thank you!

  • @ammaryildirim7721
    @ammaryildirim7721 Год назад

    9 years later here to thank you for your perfect explanation!

  • @TheHeadlets
    @TheHeadlets 6 лет назад +2

    Thank you so much for this video! Extremely helpful and clear explanation.

  • @sonicrocks2007
    @sonicrocks2007 9 лет назад +6

    Best Explanation online.

  • @surendra7714
    @surendra7714 Год назад

    My professor is too bad at teaching this. Thank you so much
    Love from Nepal🇳🇵

  • @malharjajoo7393
    @malharjajoo7393 6 лет назад +10

    So basically this is just backsubtitution.

  • @avizzzy
    @avizzzy 10 лет назад

    Not only the best explanation but also the easiest way to remember the steps.

  • @user-ro1cc8tz6d
    @user-ro1cc8tz6d 10 месяцев назад

    you're truly a good person. be proud!

  • @humaidahmedabuzinjal6257
    @humaidahmedabuzinjal6257 Год назад

    thanks to this video, i passed my finals exam on my number theory class

  • @DM-su6li
    @DM-su6li 2 года назад

    This was incredibly useful, thank you

  • @matt4825
    @matt4825 8 лет назад

    this is amazing. Thank you so much! I had been stuck for hours!

  • @ivxr.r
    @ivxr.r Месяц назад

    Euclid and Bezout were on drugs that day

  • @timothymchale7710
    @timothymchale7710 10 лет назад

    Excellent video describing how EEA is used to solve gcd(a,b) = ax+by for {x,y}

  • @Themostbeautyful
    @Themostbeautyful 5 лет назад

    Dude you are the best, thanks a lot!

  • @harshithramamurthy2820
    @harshithramamurthy2820 6 лет назад +1

    Hello Sir,
    Could you please tell me why is it important to do extended Euclidean algorithm? You said well find that out in a next video but couldn't find any video. Please help!

  • @manravsinghk
    @manravsinghk 2 года назад

    Thank you so much for this! I was stuck with discrete math and this helped so much! Hope ur doing well

  • @ThatWasherNerd
    @ThatWasherNerd 2 года назад

    Absolutely excellent explanation! Definitely will help my on my final this Friday!

  • @botme7
    @botme7 25 дней назад

    i love this explanation so much

  • @swapanjain892
    @swapanjain892 9 лет назад +4

    This is really well explained.

  • @avyakthaachar2.718
    @avyakthaachar2.718 Год назад

    Great explanation. Thank you so much 🙏

  • @andrewmartin6971
    @andrewmartin6971 6 лет назад

    At around 9:40, what do you do if the other number isn't used in the eclidean algorithm?

  • @dripfire2396
    @dripfire2396 Год назад

    Thanks for the concise explanation

  • @michaelhanna1362
    @michaelhanna1362 7 лет назад

    Thank you very much, your video was very helpful explaining the concept that I was having trouble grasping in Discrete Mathmatics.

  • @connorheckman6675
    @connorheckman6675 10 лет назад +1

    immensely helpful. Thank you good sir

  • @shadowgaleshale9218
    @shadowgaleshale9218 Год назад

    didnt get it until i found this video. thank u

  • @chenzhuo9
    @chenzhuo9 9 лет назад +20

    What is the next video btw?

    • @albert0118
      @albert0118 7 лет назад +1

      The next video is Multiplicative inverses mod n
      as posted by
      @Celebrian 1 year ago

  • @SavagiebeatsZw
    @SavagiebeatsZw 3 года назад

    thank you for the clear workings

  • @nt9864
    @nt9864 5 лет назад +1

    You're the best best best omggg this helped me so much thanks a lot! 😭❤❤

  • @mksarav75
    @mksarav75 7 лет назад

    Thank you. Beautifully explained.

  • @Abobimasamasa
    @Abobimasamasa 2 года назад

    Great tutoring,wish you were my Lecturer

  • @Blueaspen391
    @Blueaspen391 8 лет назад

    what is the benefit of expressing the gcd as a linear combination?

  • @bindumenon249
    @bindumenon249 8 лет назад

    It is indeed a beautiful explanation. It helped me a lot

  • @SekiroOnSwitch
    @SekiroOnSwitch 4 года назад

    Wonderfully explained, thank you.

  • @NPOCrushader
    @NPOCrushader 4 года назад

    THANK YOU! Wish my math teacher was able to teach this half as good....

  • @cheito63
    @cheito63 8 лет назад +20

    Sorry guys, but this is not the Extended Euclidean Algorithm. This a procedure called back substitution. en.m.wikipedia.org/wiki/Extended_Euclidean_algorithm

    • @CampaignsIlraon
      @CampaignsIlraon 7 лет назад +1

      We've learnt it under the name "coefficients de Bézout" and I think it's the exact same thing that is displayed in this video (i.e Extended Euclidean algorithm and this video are the same). But I might be mistaken.

    • @mksarav75
      @mksarav75 7 лет назад

      Beautifully said.

  • @michelledubbeldam9298
    @michelledubbeldam9298 2 месяца назад

    if someone could explain how it works when the outcome of a lineair function is a multiply of the GCD(r,s) . Try: 6600r + 505050r = 150

  • @ashuashu8154
    @ashuashu8154 7 лет назад

    Thanku sir it's too easy to understand . Well explained .

  • @josuegialis8146
    @josuegialis8146 5 лет назад

    Extremely helpful. Thank you.

  • @rikenm
    @rikenm 7 лет назад

    This is Extended:
    s_0 , s_1, t_1, t_0 are constant.
    r_i = s_i a +t_i b
    s_i is a recursive function such that s_i =( s_i-2) +( s_i-1)(q_i-1)
    t_i is also similar.
    q_i = Floor(r_i-2/r_i-1)

  • @bitcoindaddy748
    @bitcoindaddy748 Год назад

    How does this relate to RSA?

  • @black_thorned_roses
    @black_thorned_roses 9 лет назад +1

    Thank you SO MUCH! I think I actually understand it now

  • @KnightDark1233
    @KnightDark1233 6 лет назад

    Thanks this might be a dumb question but is there a way to construct a matrix and row reduce the augmented matrix to find the weights?

  • @gitrogZG
    @gitrogZG 4 года назад +1

    this is more effective than my teacher and took like a tenth of the time

  • @kp8378
    @kp8378 4 года назад

    Thanks man!!
    Help alot!!

  • @CelebornBrian
    @CelebornBrian 8 лет назад +10

    The next video is Multiplicative inverses mod n

    • @Mustafa-wv5cs
      @Mustafa-wv5cs 8 лет назад

      Celebrian Euclidean algorithm what class?
      Sorry, my english is bad.

    • @CelebornBrian
      @CelebornBrian 8 лет назад +3

      He says at the end of this video: "stay tuned for the next video", I just wanted to post that the next video in this series is /watch?v=_bRVA5b4sb4 because I found it not that easy to find myself. That video is called "Multiplicative inverses mod n"

  • @JohnNguyen-vy2cn
    @JohnNguyen-vy2cn 2 года назад

    5:41 I too, use the Euclidean Algorithm to find god

  • @thecatoftime8152
    @thecatoftime8152 2 года назад

    brilliantly explained

  • @RondellKB
    @RondellKB 9 лет назад

    This was extremely helpful, thanks a lot

  • @DUDE09JWEJVNUIBYUHBU
    @DUDE09JWEJVNUIBYUHBU 10 лет назад

    you're fucking amazing i searched like 2 hours for explain how to do this and all the others was so understandble and when i watched that i just so quick understood it your explains are so good thank you so much you are awsome!!!!!!!!!

  • @azzahrah5791
    @azzahrah5791 7 лет назад

    Thanks. It helps me a lot

  • @FoamySoaps
    @FoamySoaps 10 лет назад

    Oh thank-you so much. I was looking all over how to do this

  • @NB19273
    @NB19273 8 лет назад

    very clear and well structured explanation, thanks a lot :)

  • @deven700
    @deven700 9 лет назад

    helped me out alot; thank you

  • @elhopper3735
    @elhopper3735 5 лет назад

    Thanks! Very helpful and easy to understand

  • @user-by9qt8pb1q
    @user-by9qt8pb1q 4 года назад

    which class ya'll in?

  • @ioanaamariucai4136
    @ioanaamariucai4136 10 лет назад

    thank you ! it was really helpful :)

  • @Kevin-gm9ll
    @Kevin-gm9ll 6 лет назад

    such an amazing video thank you!

  • @wodeybrown1748
    @wodeybrown1748 2 года назад

    Great explanation!

  • @blanenaidoo4302
    @blanenaidoo4302 2 года назад

    This guy is a legend

  • @communtyhivemind
    @communtyhivemind 4 года назад

    Advent of Code brought me here

  • @Ravel1299
    @Ravel1299 9 лет назад

    Great work, thank you!

  • @jasonji3263
    @jasonji3263 5 лет назад

    Wow who knew Kermit was such a great math teacher!