Number Theory | Extended Euclidean Algorithm Example #1

We use the extended Euclidean algorithm to write the greatest common divisor of two natural numbers as a linear combination of them.

[jndd]

I've never heard of the extended euclidean algorithm before, but this seems super interesting so I'll learn it :)
Here is how I solved it, btw (before watching the video):
123x + 45y = gcd(123, 45)
Simplify that to 41x + 15y = 1
let's say k = -y (I just wanted to think of it this way, it's not necessary tho)
so 41x - 15k = 1
(41x - 15k) - 3(15x) + 3(15x) = 1
-4x - 15k + 45x = 1
4x + 15k - 45x = -1
let's say k = 3x + n (This is because we want that x term to cancel and n is just some number)
substitute that into the previous equation:
4x + 15(3x + n) - 45x = -1
4x + 15n = -1
now it's much easier so after a little guess and check, we can see 44 - 45 = -1 works. (It's only one of many other examples)
that means x = 11 and n = -3
because earlier we said that k = 3x + n and k = -y so y = -3x - n
y = -3(11) - (-3) = -33 + 3 = -30
We see that (x, y) = (11, -30) works, so yay.
Thanks for the awesome vid!

[ltrel]

Been struggling to understand this for a while and you made it beautifully clear, thank you man

[PunmasterSTP]

Thanks for our knowledge and understanding with another exceptional video!

[-couchpotato-]

It only took me 3 minutes to understand this one. My teacher explained it and I didn't get anything from what she has taught. Thanks man✊

[bonbonpony]

00:12 Which "previous video"? This video here is one of the oldest videos on your channel (the 38th video), and the last one about number theory was the 24th video "The Euclidean Algorithm Example 2". I don't see any such proof in that video :q The 37th video is on an entirely different subject (exact differential equations), and there are no other Number Theory videos between 24 and 38.

[georgesadler]

Professor M. Penn. thank you for an excellent lecture on The Extended Euclidean Algorithm.

[xxrawrgameremoxx]

youre an angel sent from heaven! thank you so much, I went from not getting anything to understanding completely! :)

[youssefelboualaoui]

bro this is literally amazing !
really helped me out

[serenaliu]

Thank uuu I finally understand what does Extended Euclidean Algorithm means! Very helpful

[АзизханУмархужаев-зз]

Thank you! I ask you to make a video about gcd properties, please.

[The_Math_Enthusiast]

I think there are infinitely many solution (solved using modular arithmetic)

[The_Math_Enthusiast]

But that is NOT A UNIQUE SOLUTION, IS IT?