Extended Euclidean Algorithm (a.k.a. the Pulverizer)
Oct 05 2020 at 17:47 GMT. The idea of the extended Euclidean algorithm is to keep track of how each encountered remainder can be written as a linear combination of a a and b b. This way, once we reach the last non-zero remainder, which corresponds to the GCD, we know how to express it as a linear combination of a a and b b.