In this video, I talk about the Extended Euclidean Algorithm, a method for solving integer equations of the form ax + by = n.

Wikipedia article: https://en.wikipedia.org/wiki/Extende...
Code: https://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