Master the Extended Euclidean Algorithm: GCD, Bezout's Theorem & Modular Inverses 🔢

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/Extended_Euclidean_algorithm
Code: https://github.com/womogenes/extended-euclidean-algo

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