Extended Euclidean Algorithm

Computing the greatest common divisor of two integers together with the coefficients of Bezout's identity.

Beyond the GCD

The Euclidean algorithm finds gcd(a, b) by repeatedly replacing the larger number with its remainder modulo the smaller. The extended version additionally returns integers x and y satisfying a*x + b*y = gcd(a, b), known as Bezout's identity. These coefficients are what make modular inverses and linear Diophantine equations solvable.

Tracking the coefficients

Kronos motion — classical

At each step the algorithm expresses the current remainder as a combination of the original a and b. Unwinding the recursion, or carrying the coefficients forward iteratively, yields x and y when the remainder reaches zero and the previous remainder is the gcd. The whole computation is O(log(min(a, b))).

Iterative version

python

def ext_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q*r
        old_s, s = s, old_s - q*s
        old_t, t = t, old_t - q*t
    return old_r, old_s, old_t   # gcd, x, y

Modular inverse

If gcd(a, m) = 1, then a*x + m*y = 1, so x mod m is the modular inverse of a. This is the general way to invert modulo any m, and unlike Fermat's little theorem it does not require m to be prime. It is a core step in the RSA key setup and the Chinese remainder theorem.

Uses

Solving linear Diophantine equations a*x + b*y = c.
Combining congruences with the Chinese remainder theorem.
Computing inverses for modular arithmetic and cryptography.
Reducing fractions and rational arithmetic exactly.