GCD, Bezout, and Modular Inverses | The Extended Euclidean Algorithm

In this video, I talk about the Extended Euclidean Algorithm, a method for solving integer equations of the form ax + by = n.
Wikipedia article: en.wikipedia.org/wiki/Extende...
Code: github.com/womogenes/extended...
00:00 Intro
00:34 The gcd function
01:48 The standard Euclidean algorithm
05:28 Implementing the standard Euclidean algorithm
07:22 Extending the Euclidean algorithm
08:08 Worked example
15:14 Generalization
16:40 Implementing the Extended Euclidean Algorithm
18:42 Application - modular inverses
21:16 Summary

[@voltflake]

Man, your videos are some of the best youtube/internet has about this topic. Thank you so much!

[@aiham224]

I F agree, i have been struggling for days to understand this

[@tanhnguyen2025]

very easy to understand.

[@jdhp3696]

Thanks for the awesome video.

[@januaryjohnson8107]

Great video! Thanks so much!!

[@Luke-jh5hi]

Second semester Computer Science and thanks to you I believe I'll graduate one day 😁

[@fredpim11]

great video and explanation maybe something on "the baby step giant step algorythm... on the continuation... thanks for your share

[@AlexTurbo]

thank you

[@thomasyang9517]

good vid

[@Lucas-pj9ns]

is there any guarantees on the maximum size of x and y? trying to code this up in c++ and im worried about overflow

[@TheStephenShu]

I found 77(23)+30(-59)=1. I wonder how to find different solutions

[@fredpim11]

when you get one particular solution you get every other ones: 77a + 30b=1 one solution you get is a=23 and b=-59 here you have to think at this form 77a=1mod 30 and 30b=1mod77 the other solutions of a are mod30 and mod 77 for b a are more or minus 30 and b are more or minus 77 a=-7, b=18 a=23, b=-59 a=-37, b=95 a=53,b=-137 etc...

[@skaunov_code]

I guess it doesn't take polynomials into account? Is there a version with them? X)

[@Luke-jh5hi]

And please make a video about RSA🙏