This algorithm helps us not only get gcd(a, b), but also get i and j so that g = gcd(a, b) = ai + bj

If $a$ and $b$ are integers, not both zero, then their greatest common divisor $g$ equals $ai + bj$ for some integers i and j (can be negative, remember).

Extended Euclid algirithm, complexity: O(lg e) Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2006)