the extended Euclidean algorithm

Euclid's algorithm finds the greatest common divisor of two numbers by the old trick of repeatedly replacing the larger number with its remainder against the smaller: gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6. The extended version does the same descent but also tracks how to write that gcd as a combination of the two original numbers. It returns not just g = gcd(a, b) but a pair of integers x, y such that a*x + b*y = g. Those coefficients are exactly what you need to compute modular inverses and to solve the Chinese remainder theorem.

Here is why such x, y exist and how to get them. Bezout's identity guarantees integers x, y with a*x + b*y = gcd(a, b). The extended algorithm builds them by unwinding the recursion: at the base case gcd(g, 0) = g, you have g = g*1 + 0*0, so x = 1, y = 0. Going back up one level, if the recursive call on (b, a mod b) returned coefficients (x', y') with b*x' + (a mod b)*y' = g, then since a mod b = a - floor(a/b)*b, a little algebra gives the coefficients for (a, b): the new x is y', and the new y is x' - floor(a/b)*y'. Each level just rewrites the combination in terms of the level above. A trace for a=48, b=18: gcd descends to (6,0) returning (1,0), and unwinding back up yields 48*(-1) + 18*(3) = -48 + 54 = 6, so x=-1, y=3.

This matters because the coefficients unlock arithmetic that plain GCD cannot. If gcd(a, m) = 1, the extended algorithm gives x with a*x + m*y = 1, which means a*x is 1 mod m, so x is the modular inverse of a — the single most common use, and the cornerstone of RSA decryption and division in modular arithmetic. The algorithm runs in O(log(min(a,b))) division steps, the same as plain Euclid, because the remainders shrink fast (a classic fact: they at least halve every two steps). Honest caveat: x and y are not unique (you can add multiples of b/g to x and subtract the matching multiple of a/g from y), and they can be negative, so for a clean modular inverse you take x mod m to land in the range 0..m-1.