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.

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!

[Luke-jhhi]

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

[fredpim]

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

[Lucas-pjns]

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

[skaunov_code]

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