The Euclidean algorithm and Bézout’s identity

Lesson 1 noticed that a common divisor of two numbers also divides their differences and other combinations. Pushed to its conclusion, that observation gives the Euclidean algorithm, a procedure for finding the greatest common divisor of two numbers that is more than 2,300 years old and still one of the fastest algorithms known for anything. Its by-product, Bézout's identity, is the key to almost everything that follows: unique factorization, solving congruences, inverses modulo \(n\) and the RSA private key.

Greatest common divisors

Definition. Let \(a\) and \(b\) be integers, not both 0. The greatest common divisor \(\gcd(a, b)\) is the largest integer that divides both \(a\) and \(b\). If \(\gcd(a, b) = 1\) we say \(a\) and \(b\) are relatively prime, or coprime.

The gcd exists because 1 is a common divisor and every common divisor is at most \(\max(|a|, |b|)\) when that is nonzero. For example the positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24, those of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36, and the largest common one is 12, so \(\gcd(24, 36) = 12\). Also \(\gcd(8, 15) = 1\) though neither number is prime, \(\gcd(a, 0) = |a|\), and \(\gcd(a, b) = \gcd(|a|, |b|)\). Listing divisors works for small numbers but is hopeless for numbers with hundreds of digits. The Euclidean algorithm needs no factorization at all.

The key lemma

Lemma. If \(a = qb + r\), then \(\gcd(a, b) = \gcd(b, r)\).

Proof. If \(d\) divides \(a\) and \(b\), it divides \(r = a - qb\). Conversely, if \(d\) divides \(b\) and \(r\), it divides \(a = qb + r\). So the pairs \((a, b)\) and \((b, r)\) have exactly the same common divisors, and in particular the same greatest one.

The point is that \(r\) is smaller than \(b\). Replacing \((a, b)\) by \((b, r)\) shrinks the numbers without changing the gcd, and we can repeat until the remainder is 0.

The Euclidean algorithm

To compute \(\gcd(a, b)\) with \(a \ge b > 0\), apply the division algorithm repeatedly: \[a = q_1b + r_1,\quad b = q_2r_1 + r_2,\quad r_1 = q_3r_2 + r_3,\quad \ldots,\quad r_{n-1} = q_{n+1}r_n + 0.\] The remainders strictly decrease, \(b > r_1 > r_2 > \cdots \ge 0\), so the process must reach remainder 0. By the lemma, \(\gcd(a, b) = \gcd(b, r_1) = \cdots = \gcd(r_n, 0) = r_n\): the gcd is the last nonzero remainder.

Example: \(\gcd(1071, 462)\). We have \(1071 = 2 \cdot 462 + 147\), \(462 = 3 \cdot 147 + 21\), \(147 = 7 \cdot 21 + 0\). The last nonzero remainder is 21, so \(\gcd(1071, 462) = 21\). Check: \(1071 = 21 \cdot 51\) and \(462 = 21 \cdot 22\), and 51 and 22 are coprime.

The figure gives the geometric picture Euclid himself had in mind. Each division step cuts as many \(b \times b\) squares as possible from an \(a \times b\) rectangle, leaving a \(b \times r\) rectangle. The process ends when the leftover rectangle is tiled exactly by squares, and the side of those squares is a common measure of the original lengths. Greek mathematicians called the procedure anthyphairesis, repeated mutual subtraction. Applied to the side and diagonal of a square or a regular pentagon, it never stops, and that is one way to see that \(\sqrt 2\) and the golden ratio are irrational.

How fast is it?

The algorithm is remarkably fast. Every two steps at least halve the remainder: if \(r_{k+1} \le r_k/2\) we are done, and otherwise \(r_{k+2} = r_k - r_{k+1} < r_k/2\) since \(r_k = 1 \cdot r_{k+1} + r_{k+2}\) in that case. So the number of steps is at most about \(2\log_2 b\), which is linear in the number of digits. For two 300-digit numbers that is at most about 2,000 steps, a fraction of a millisecond on a computer. Gabriel Lamé proved in 1844 the sharper bound that the number of steps is at most five times the number of decimal digits of the smaller number, and that the worst case occurs for consecutive Fibonacci numbers: \(\gcd(F_{n+1}, F_n)\) takes the most steps for its size, because every quotient is 1. This was one of the first results in the analysis of algorithms.

Bézout's identity

Running the algorithm backwards gives more than the gcd.

Theorem (Bézout's identity). If \(a\) and \(b\) are not both 0, there are integers \(x\) and \(y\) such that \[ax + by = \gcd(a, b).\] Moreover, \(\gcd(a, b)\) is the smallest positive integer of the form \(ax + by\), and the integers of that form are exactly the multiples of \(\gcd(a, b)\).

Proof. Let \(S = \{ax + by > 0 : x, y \in \mathbb{Z}\}\). It is nonempty (it contains \(a^2 + b^2\)), so by well-ordering it has a least element \(d = ax_0 + by_0\). Divide \(a\) by \(d\): \(a = qd + r\) with \(0 \le r < d\). Then \(r = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)\) is of the same form. If \(r > 0\) it would be an element of \(S\) smaller than \(d\), so \(r = 0\) and \(d \mid a\). Similarly \(d \mid b\), so \(d\) is a common divisor and \(d \le \gcd(a, b)\). On the other hand \(\gcd(a, b)\) divides \(a\) and \(b\), hence divides \(ax_0 + by_0 = d\), so \(\gcd(a, b) \le d\). Thus \(d = \gcd(a, b)\). Every combination \(ax + by\) is a multiple of the gcd, and every multiple \(k\gcd(a, b) = a(kx_0) + b(ky_0)\) is a combination.

Corollary. Every common divisor of \(a\) and \(b\) divides \(\gcd(a, b)\). So the gcd is greatest not only in size but in the divisibility sense too. Corollary: \(a\) and \(b\) are coprime if and only if \(ax + by = 1\) for some integers \(x, y\). That gives a quick certificate: \(\gcd(8, 15) = 1\) because \(8 \cdot 2 + 15 \cdot (-1) = 1\).

The extended Euclidean algorithm

The proof of Bézout's identity shows that \(x\) and \(y\) exist but does not find them. To find them, keep track of how each remainder is a combination of \(a\) and \(b\). Back-substitution works by hand: from the computation of \(\gcd(1071, 462)\), \[21 = 462 - 3 \cdot 147 = 462 - 3(1071 - 2 \cdot 462) = 7 \cdot 462 - 3 \cdot 1071.\] So \(x = -3\), \(y = 7\) works: \(1071(-3) + 462 \cdot 7 = -3213 + 3234 = 21\).

A cleaner method carries the coefficients forward. Write each remainder as \(r_k = ax_k + by_k\), starting from \(r_{-1} = a = a \cdot 1 + b \cdot 0\) and \(r_0 = b = a \cdot 0 + b \cdot 1\). Since \(r_{k+1} = r_{k-1} - q_{k+1}r_k\), the coefficients obey the same recurrence: \(x_{k+1} = x_{k-1} - q_{k+1}x_k\), and likewise for \(y\). This is the extended Euclidean algorithm, and it is how computers find modular inverses. The table form for \(a = 240\), \(b = 46\):

Check: \(240 \cdot (-9) + 46 \cdot 47 = -2160 + 2162 = 2\), and indeed \(\gcd(240, 46) = 2\).

The coefficients are not unique. If \(ax + by = d\), then also \(a(x + b/d \cdot t) + b(y - a/d \cdot t) = d\) for every integer \(t\). For 240 and 46, \(x = -9 + 23t\), \(y = 47 - 120t\): for example \(x = 14\), \(y = -73\).

Euclid's lemma

The most important consequence of Bézout's identity is the following lemma, which the next lesson uses to prove unique factorization.

Theorem. If \(a \mid bc\) and \(\gcd(a, b) = 1\), then \(a \mid c\).

Proof. Write \(ax + by = 1\). Multiply by \(c\): \(acx + bcy = c\). Now \(a\) divides \(acx\), and \(a\) divides \(bcy\) because \(a \mid bc\). So \(a\) divides their sum \(c\).

The coprimality hypothesis matters: \(6 \mid 4 \cdot 9\) but 6 divides neither 4 nor 9. Two more consequences of the same kind: if \(a \mid c\), \(b \mid c\) and \(\gcd(a, b) = 1\), then \(ab \mid c\) (write \(c = ak\); then \(b \mid ak\) with \(\gcd(a, b) = 1\), so \(b \mid k\)), which completes the argument about three consecutive integers in lesson 1. And if \(d = \gcd(a, b)\), then \(\gcd(a/d, b/d) = 1\), since dividing \(ax + by = d\) by \(d\) gives \((a/d)x + (b/d)y = 1\). That is why reducing a fraction by the gcd gives lowest terms.

Least common multiples

The least common multiple \(\operatorname{lcm}(a, b)\) of positive integers is the smallest positive integer divisible by both. It is related to the gcd by \[\gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab.\] Proof sketch: let \(d = \gcd(a, b)\) and \(m = ab/d\). Then \(m = a(b/d) = b(a/d)\) is a common multiple. If \(c\) is any common multiple, write \(c = ak\); then \(b \mid ak\), so \((b/d) \mid (a/d)k\), and since \(a/d\) and \(b/d\) are coprime, \((b/d) \mid k\), so \(m = a(b/d)\) divides \(c\). So \(\operatorname{lcm}(240, 46) = 240 \cdot 46/2 = 5520\). Computing an lcm through the gcd avoids factoring, and this is how fractions are put over a common denominator efficiently.

Bézout by computer

The program implements the Euclidean algorithm and its extended form, reproduces the table above, verifies Bézout's identity on thousands of random pairs, and counts division steps for consecutive Fibonacci numbers to illustrate Lamé's worst case.

import math, random

def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

def ext_gcd(a, b):
    """Return (g, x, y) with a*x + b*y = g = gcd(a, b)."""
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b:
        q = a // b
        a, b = b, a - q * b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

print("gcd(1071, 462) =", gcd(1071, 462))
print("ext_gcd(240, 46) =", ext_gcd(240, 46))
print("ext_gcd(1071, 462) =", ext_gcd(1071, 462))

random.seed(1)
ok = True
for _ in range(5000):
    a, b = random.randint(1, 10**12), random.randint(1, 10**12)
    g, x, y = ext_gcd(a, b)
    ok &= (a * x + b * y == g == math.gcd(a, b))
print("Bezout verified on 5000 random pairs:", ok)

def steps(a, b):
    n = 0
    while b:
        a, b, n = b, a % b, n + 1
    return n

fib = [1, 1]
while len(fib) < 30:
    fib.append(fib[-1] + fib[-2])
print("steps for (F31, F30):", steps(fib[29] + fib[28], fib[29]), " digits of F30:", len(str(fib[29])))
big1, big2 = 3**200 + 1, 2**300 + 7
print("steps for two ~95-digit numbers:", steps(big1, big2), " gcd:", gcd(big1, big2))

gcd(1071, 462) = 21
ext_gcd(240, 46) = (2, -9, 47)
ext_gcd(1071, 462) = (21, -3, 7)
Bezout verified on 5000 random pairs: True
steps for (F31, F30): 29  digits of F30: 6
steps for two ~95-digit numbers: 174  gcd: 1

The extended algorithm returns \(x = -9\), \(y = 47\) for 240 and 46, matching the table. The 6-digit Fibonacci pair needs 29 steps, one per term and just inside Lamé's bound of five steps per digit, while two numbers with more than 90 digits each need only 174 steps, in line with the logarithmic bound. Python's math.gcd uses the same idea, with refinements for very large numbers.