modular arithmetic - How do the Euclidean and extended Euclidean algorithms work?

One can use the extended Euclidean algorithm to calculate the modular multiplicative inverse of a number, as it will be in the form $a x + b y = 1$, and if you take mod $b$ of both sides you get the inverse of $a$ in mod $b$. However, why does the Euclidean algorithm work? Specifically, why is the last non-zero remainder gcd(a,b)? And how come you can just substitute everything back and it magically give you gcd(a,b) in terms of integers? Thanks so much.