21.01.01 · number-theory / elementary

Divisibility, GCD, Bézout's identity, and the Euclidean algorithm

shipped3 tiersLean: none

Anchor (Master): Euclid c. 300 BCE *Elements* Book VII Props. 1-2 (originator of the algorithm); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e (Oxford, revised Heath-Brown-Silverman-Wiles) §§I-II; Lang 2002 *Algebra* (Springer GTM 211, 3e) Ch. II §1 (Euclidean rings and principal ideal domains); Knuth 1997 *The Art of Computer Programming, Vol. 2: Seminumerical Algorithms* 3e §4.5.2 (greatest common divisor); Lamé 1844 *Comptes Rendus* 19 (Fibonacci worst case); Stein 1967 *J. Comput. Phys.* 1 (binary GCD)

Intuition Beginner

Divisibility is the most basic question you can ask about two whole numbers. Given $12$ and $3$ , you can split $12$ into four equal piles of $3$ with nothing left over, so $3$ divides $12$ . Given $12$ and $5$ , you cannot — you get two piles of $5$ and a remainder of $2$ . The whole subject of number theory begins with this single question and the patterns that emerge when you ask it across many pairs of integers.

The greatest common divisor of two positive integers is the largest whole number that divides both. The gcd of $12$ and $18$ is $6$ , because $6$ divides both ( $12 = 2 \times 6$ and $18 = 3 \times 6$ ) and no larger number does. The gcd shows up everywhere: simplifying fractions, finding common periods, deciding when two clocks tick in unison, and analysing the structure of cyclic groups.

The Euclidean algorithm is an old and elegant procedure for computing the gcd quickly. Instead of factoring both numbers and comparing factors, you replace the larger number by the remainder when it is divided by the smaller, and repeat. The numbers shrink fast, and the last nonzero remainder is the gcd. The method dates to Euclid's Elements around $300$ BCE and is still the algorithm a modern computer uses.

Bézout's identity is the beautiful side of this story. It says that the gcd of $a$ and $b$ is always reachable as a sum $a x + b y$ with $x$ and $y$ whole numbers (one of which is usually negative). The gcd of $12$ and $18$ is $6$ , and indeed $6 = 12 \times (- 1) + 18 \times 1$ . Combinations of $12$ and $18$ exactly fill the multiples of $6$ .

Visual Beginner

A diagram of two stacks of boxes side by side, one of height $18$ and one of height $12$ . The procedure removes the smaller stack from the larger as many times as it fits, leaving a stack of height $6$ . Then the procedure repeats with the new pair $(12, 6)$ , where $12$ contains two copies of $6$ exactly, leaving a stack of height $0$ . The last nonzero remainder, $6$ , is the gcd. A line at the bottom shows the Bézout combination $6 = 18 - 12$ .

The picture captures the entire algorithm in two steps. The number on the right side keeps shrinking until it hits zero, and the previous nonzero value is the answer. The Bézout combination is the bookkeeping that records how the answer was assembled from the original two numbers.

Worked example Beginner

Compute the gcd of $252$ and $105$ using the Euclidean algorithm, then write the gcd as a combination $252 x + 105 y$ .

Step 1. Divide $252$ by $105$ : $252 = 2 \times 105 + 42$ . The remainder is $42$ , so replace the pair $(252, 105)$ by $(105, 42)$ .

Step 2. Divide $105$ by $42$ : $105 = 2 \times 42 + 21$ . The remainder is $21$ , so replace $(105, 42)$ by $(42, 21)$ .

Step 3. Divide $42$ by $21$ : $42 = 2 \times 21 + 0$ . The remainder is $0$ , so the algorithm stops. The last nonzero remainder is $21$ , so $g cd (252, 105) = 21$ .

Step 4. Reverse the chain to find the Bézout coefficients. From Step 2: $21 = 105 - 2 \times 42$ . From Step 1: $42 = 252 - 2 \times 105$ . Substitute the second into the first:

$21 = 105 - 2 \times (252 - 2 \times 105) = 105 - 2 \times 252 + 4 \times 105 = 5 \times 105 - 2 \times 252.$

So $21 = 252 \times (- 2) + 105 \times 5$ . Check: $- 504 + 525 = 21$ .

What this tells us: three division steps produce both the gcd $21$ and the explicit coefficients $x = - 2$ , $y = 5$ . The reverse pass is just bookkeeping — every gcd computation carries inside it an explicit recipe for writing the gcd as an integer combination of the original two numbers.

Check your understanding Beginner

Formal definition Intermediate+

Divisibility, the greatest common divisor, and Bézout coefficients admit clean definitions in the ring of integers $Z$ . The Euclidean algorithm is the constructive bridge between them.

Definition (divisibility). For integers $a, b \in Z$ , we say $a$ divides $b$ , written $a ∣ b$ , if there exists an integer $c \in Z$ with $b = a c$ . The relation $∣$ is reflexive ( $a ∣ a$ ), transitive ( $a ∣ b$ and $b ∣ c$ imply $a ∣ c$ ), and respects linear combinations ( $a ∣ b$ and $a ∣ c$ imply $a ∣ (mb + n c)$ for all $m, n \in Z$ ).

Definition (greatest common divisor). For $a, b \in Z$ not both zero, the greatest common divisor $g cd (a, b)$ is the unique positive integer $d$ such that

$d ∣ a$ and $d ∣ b$ (common divisor), and
for every $e \in Z$ with $e ∣ a$ and $e ∣ b$ , we have $e ∣ d$ (universal among common divisors).

Equivalently, $g cd (a, b)$ is the largest positive integer dividing both $a$ and $b$ under the natural-number ordering; condition (2) sharpens "largest" to a universal property that survives the ring-theoretic generalisation. By convention $g cd (0, 0) = 0$ .

Definition (Bézout coefficients). Integers $x, y \in Z$ satisfying $a x + b y = g cd (a, b)$ are called Bézout coefficients for the pair $(a, b)$ . They are not unique: if $(x, y)$ is a Bézout pair and $d = g cd (a, b)$ , then $(x + b / d \cdot t, y - a / d \cdot t)$ is also a Bézout pair for every $t \in Z$ .

Definition (Euclidean algorithm). Given $a, b \in Z$ with $a \geq b > 0$ , the Euclidean algorithm produces a sequence of remainders by repeated division-with-remainder:

a = q_{1} b + r_{1}, 0 \leq r_{1} < b, b = q_{2} r_{1} + r_{2}, 0 \leq r_{2} < r_{1}, r_{1} = q_{3} r_{2} + r_{3}, \dots

The remainders $r_{1} > r_{2} > r_{3} > \dots \geq 0$ strictly decrease, so the sequence terminates at some $r_{n} = 0$ . The last nonzero remainder $r_{n - 1}$ is the gcd of $a$ and $b$ .

Counterexamples to common slips

" $0$ divides $0$ is false because you cannot divide by zero." Under the definition above, $0 ∣ 0$ holds: setting $c = 17$ (or any integer) gives $0 = 0 \times c$ . The everyday-arithmetic prohibition against dividing by zero concerns the fraction $0/0$ being undefined, not the divisibility relation $∣$ . The integer $g cd (0, 0) = 0$ is then a convention chosen so that gcd is associative and respects the ideal-theoretic definition $g cd (a, b) =$ generator of $Z a + Z b$ , with $Z \cdot 0 + Z \cdot 0 = {0} = Z \cdot 0$ .
"The Bézout coefficients are unique." The pair $(x, y)$ with $a x + b y = g cd (a, b)$ is determined only up to shifts by multiples of the orthogonal lattice direction. For $g cd (252, 105) = 21$ , the pair $(- 2, 5)$ works ( $- 504 + 525 = 21$ ), and so does $(- 2 + 5 t, 5 - 12 t)$ for every $t \in Z$ , since $5 = 105/21$ and $12 = 252/21$ .
"The Euclidean algorithm requires $a, b > 0$ ." Strictly the algorithm makes sense for any $a, b \in Z$ with at least one nonzero, after reduction to the positive case via $g cd (a, b) = g cd (∣ a ∣, ∣ b ∣)$ . The recursion $g cd (a, b) = g cd (b, a mod b)$ stays well-defined when $b = 0$ via the base case $g cd (a, 0) = ∣ a ∣$ .

Key theorem with proof Intermediate+

The signature theorem of this unit is Bézout's identity, the existence statement underlying every later application of the Euclidean algorithm (modular inverses, the structure of $Z$ as a PID, RSA, the Chinese remainder theorem). We prove it via the well-ordering principle on the set of positive integer linear combinations.

Theorem (Bézout's identity). For integers $a, b \in Z$ not both zero, there exist integers $x, y \in Z$ such that

a x + b y = g cd (a, b) .

Moreover, $g cd (a, b)$ equals the smallest positive integer in the set ${a x + b y : x, y \in Z}$ .

Proof. Let $S = {a x + b y : x, y \in Z, a x + b y > 0}$ be the set of positive integer linear combinations of $a$ and $b$ . Since $a$ and $b$ are not both zero, at least one of $∣ a ∣ = a \cdot sgn (a) + b \cdot 0$ or $∣ b ∣$ lies in $S$ , so $S$ is non-empty. By the well-ordering principle on $N$ , $S$ has a least element $d = a x_{0} + b y_{0}$ for some $x_{0}, y_{0} \in Z$ .

We claim $d = g cd (a, b)$ . First, $d ∣ a$ : divide $a$ by $d$ with remainder, $a = q d + r$ with $0 \leq r < d$ . Then

r = a - q d = a - q (a x_{0} + b y_{0}) = a (1 - q x_{0}) + b (- q y_{0}),

so $r$ is an integer linear combination of $a$ and $b$ . If $r > 0$ , then $r \in S$ and $r < d$ , contradicting the minimality of $d$ . Hence $r = 0$ , and $d ∣ a$ . By the symmetric argument, $d ∣ b$ .

Next, $d$ is universal: if $e \in Z$ satisfies $e ∣ a$ and $e ∣ b$ , then $e ∣ (a x_{0} + b y_{0}) = d$ . The two conditions characterising the gcd are satisfied, so $d = g cd (a, b)$ . Since $d \in S$ , this proves the moreover statement: $g cd (a, b)$ is the smallest positive element of the set of integer linear combinations of $a$ and $b$ . $□$

Bridge. Bézout's identity builds toward 01.02.06 commutative rings and ideals, where the proof above reappears in the form "the principal ideal $(a) + (b) = (d)$ with $d = g cd (a, b)$ ", and the central insight is exactly the bridge from the ring-theoretic statement that $Z$ is a principal ideal domain to the analytic statement that every additive subgroup of $R$ generated by integers is cyclic. The foundational reason the well-ordering argument works is that $N$ admits the strong-induction principle of 00.12.01, which is exactly the categorical content of being a well-founded recursion target. Putting these together identifies the Euclidean algorithm with a well-founded recursion on the lexicographic ordering of the pair $(max (a, b), min (a, b))$ , generalises to every Euclidean domain (the polynomial ring $k [X]$ , the Gaussian integers $Z [i]$ , the Eisenstein integers $Z [ω]$ ), and appears again in 21.01.04 the fundamental theorem of arithmetic, whose proof reduces via Bézout to Euclid's Lemma (a prime dividing $ab$ divides $a$ or $b$ ).

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that $g cd (a, b) = g cd (b, a - q b)$ for any integers $a, b$ with $b \neq = 0$ and any integer $q$ . (This is the correctness lemma underlying the Euclidean recursion.)

Hint

Show that the set of common divisors of $(a, b)$ equals the set of common divisors of $(b, a - q b)$ ; then the maximum element of the two sets coincides.

Answer

Let $d ∣ a$ and $d ∣ b$ . Then $d ∣ (a - q b)$ , so $d$ divides both $b$ and $a - q b$ . Conversely, let $e ∣ b$ and $e ∣ (a - q b)$ . Then $e ∣ ((a - q b) + q b) = a$ , so $e$ divides both $a$ and $b$ . The two sets of common divisors coincide; their largest positive element is therefore the same. Hence $g cd (a, b) = g cd (b, a - q b)$ .

In particular, taking $q$ to be the quotient in division-with-remainder $a = q b + r$ , we get $g cd (a, b) = g cd (b, r)$ , which is the recursive identity driving the Euclidean algorithm.

Rubric: full credit for the symmetric divisor-set argument.

Exercise 4 (medium, symbolic).

Prove Euclid's Lemma: if $p$ is a prime and $p ∣ ab$ for integers $a, b$ , then $p ∣ a$ or $p ∣ b$ .

Hint

If $p ∤ a$ , then $g cd (p, a) = 1$ because the only positive divisors of $p$ are $1$ and $p$ . Use Bézout to write $1 = p u + a v$ , multiply through by $b$ , and read off the conclusion.

Answer

Suppose $p ∣ ab$ and $p ∤ a$ . The positive divisors of $p$ are exactly $1$ and $p$ (the definition of prime), and $p ∤ a$ means $p$ is not among the common divisors of $p$ and $a$ . Hence $g cd (p, a) = 1$ . By Bézout, there exist integers $u, v$ with $p u + a v = 1$ . Multiply by $b$ : $p u b + a v b = b$ . Now $p ∣ p u b$ directly (rewrite as $p ∣ p (u b)$ ), and $p ∣ ab$ by hypothesis, so $p ∣ a v b$ . Adding, $p ∣ (p u b + a v b) = b$ .

Rubric: full credit for using Bézout to convert "coprime" into a usable linear identity. Partial credit for stating the lemma without applying Bézout.

Exercise 5 (medium, symbolic).

Prove that the Euclidean algorithm terminates. Specifically, show that for $a > b > 0$ , the remainder sequence $r_{1}, r_{2}, r_{3}, \dots$ defined by $r_{- 1} = a$ , $r_{0} = b$ , and $r_{i + 1} = r_{i - 1} mod r_{i}$ strictly decreases and reaches $0$ in finitely many steps.

Hint

The remainder $r_{i + 1}$ satisfies $0 \leq r_{i + 1} < r_{i}$ by definition of division-with-remainder. A strictly decreasing sequence of non-negative integers cannot continue indefinitely.

Answer

By definition of division-with-remainder, $0 \leq r_{i + 1} < r_{i}$ . The sequence $r_{0} > r_{1} > r_{2} > \dots \geq 0$ is therefore a strictly decreasing sequence of non-negative integers. By the well-ordering principle (or equivalently, strong induction on $r_{0} = b$ ), no such sequence can have more than $b + 1$ terms; some $r_{n} = 0$ within at most $b$ steps. The algorithm terminates at the first such $r_{n}$ .

In fact a much stronger bound holds: the Lamé bound (Master tier, Theorem 2 below) gives $n = O (lo g b)$ , but the elementary well-ordering argument suffices for termination.

Rubric: full credit for invoking well-ordering on the strictly decreasing sequence; bonus credit for noting the stronger logarithmic bound.

Exercise 6 (medium, symbolic).

Prove that for any integers $a, b$ not both zero and any positive integer $m$ , $g cd (ma, mb) = m \cdot g cd (a, b)$ .

Hint

Use the Bézout characterisation: $g cd (a, b)$ is the smallest positive value of $a x + b y$ . Multiply the corresponding identity by $m$ .

Answer

Let $d = g cd (a, b)$ . By Bézout, $d = a x_{0} + b y_{0}$ for some integers $x_{0}, y_{0}$ . Multiply by $m$ : $m d = (ma) x_{0} + (mb) y_{0}$ , so $m d$ is a positive integer linear combination of $ma$ and $mb$ ; hence $m d \geq g cd (ma, mb)$ .

Conversely, $m d ∣ ma$ and $m d ∣ mb$ (because $d ∣ a$ and $d ∣ b$ imply $m d ∣ ma$ and $m d ∣ mb$ ), so $m d$ is a common divisor of $ma$ and $mb$ ; hence $m d \leq g cd (ma, mb)$ in the divisibility order, and since both sides are positive integers, $m d \leq g cd (ma, mb)$ . Combining the two inequalities, $g cd (ma, mb) = m d = m g cd (a, b)$ .

Rubric: full credit for the double-inequality argument; deduct for asserting only one direction.

Exercise 7 (hard, symbolic).

State and prove the extended Euclidean algorithm: given $a, b \in Z$ with $b \neq = 0$ , design a recursion that returns the triple $(d, x, y)$ with $d = g cd (a, b)$ and $a x + b y = d$ .

Hint

Recurse on $g cd (b, a mod b)$ . If the recursive call returns $(d, x^{'}, y^{'})$ with $b x^{'} + (a mod b) y^{'} = d$ , substitute $a mod b = a - ⌊ a / b ⌋ b$ and read off the new coefficients.

Answer

Algorithm. Define $extGCD (a, b)$ by:

Base case: if $b = 0$ , return $(a, 1, 0)$ (since $a \times 1 + 0 \times 0 = a = g cd (a, 0)$ ).
Recursive case: let $q = ⌊ a / b ⌋$ and $r = a - q b = a mod b$ . Recursively call $(d, x^{'}, y^{'}) = extGCD (b, r)$ . Return $(d, y^{'}, x^{'} - q y^{'})$ .

Correctness. By induction on $max (a, b)$ (lexicographic on the pair, or equivalently on $b$ ). The base case $(a, 0)$ is direct. For the inductive step, by the recursive hypothesis $b x^{'} + r y^{'} = d$ ; substituting $r = a - q b$ :

b x^{'} + (a - q b) y^{'} = d ⟹ a y^{'} + b (x^{'} - q y^{'}) = d .

Reading off the coefficients, $x_{new} = y^{'}$ and $y_{new} = x^{'} - q y^{'}$ , which is the recursion above.

Termination. Identical to the ordinary Euclidean algorithm: the second argument strictly decreases, so the recursion reaches $b = 0$ in finitely many steps.

Worked instance. $extGCD (252, 105) \to extGCD (105, 42) \to extGCD (42, 21) \to extGCD (21, 0) = (21, 1, 0)$ . Unwinding: at $(42, 21)$ , $q = 2$ , returns $(21, 0, 1)$ ; at $(105, 42)$ , $q = 2$ , returns $(21, 1, - 2)$ ; at $(252, 105)$ , $q = 2$ , returns $(21, - 2, 5)$ . Hence $252 \times (- 2) + 105 \times 5 = - 504 + 525 = 21$ .

Rubric: full credit for the recursion, the inductive correctness argument, and a worked instance verifying the Bézout identity.

Exercise 8 (hard, symbolic).

A modular inverse of $a$ modulo $m$ is an integer $a^{- 1}$ with $a \cdot a^{- 1} \equiv 1 (mod m)$ . Show that $a$ has a modular inverse mod $m$ if and only if $g cd (a, m) = 1$ , and that when it exists the inverse is unique modulo $m$ and computable from the extended Euclidean algorithm.

Hint

Use Bézout in one direction: if $g cd (a, m) = 1$ then $a x + m y = 1$ , so $a x \equiv 1 (mod m)$ . For the converse, $a \cdot a^{- 1} \equiv 1 (mod m)$ means $a a^{- 1} - 1 = m t$ for some integer $t$ , so $a a^{- 1} - m t = 1$ .

Answer

Existence ( $\Leftarrow$ ). Suppose $g cd (a, m) = 1$ . By Bézout, there exist integers $x, y$ with $a x + m y = 1$ . Reducing modulo $m$ : $a x \equiv 1 (mod m)$ . So $x$ is a modular inverse of $a$ modulo $m$ . The integer $x$ is computed by the extended Euclidean algorithm of Exercise 7 applied to $(a, m)$ .

Existence ( $\Rightarrow$ ). Suppose $a a^{- 1} \equiv 1 (mod m)$ , i.e. $a a^{- 1} - 1 = m t$ for some integer $t$ . Rearrange: $a a^{- 1} - m t = 1$ , which is an integer linear combination of $a$ and $m$ equal to $1$ . By Bézout, $g cd (a, m) ∣ 1$ , so $g cd (a, m) = 1$ .

Uniqueness. If $x_{1}$ and $x_{2}$ are both modular inverses, $a (x_{1} - x_{2}) \equiv 0 (mod m)$ . Since $g cd (a, m) = 1$ , Euclid's Lemma (Exercise 4 applied to a prime power decomposition, or directly from Bézout) gives $m ∣ (x_{1} - x_{2})$ , so $x_{1} \equiv x_{2} (mod m)$ .

Computational note. For $a = 7$ , $m = 26$ , the extended Euclidean algorithm yields $7 \times (- 11) + 26 \times 3 = 1$ , so $7^{- 1} \equiv - 11 \equiv 15 (mod 26)$ . Check: $7 \times 15 = 105 = 4 \times 26 + 1$ .

This is the load-bearing arithmetic step underlying RSA: the private exponent is the modular inverse of the public exponent modulo $ϕ (N)$ , and its computation is by extended Euclidean.

Rubric: full credit for both directions of the biconditional, the uniqueness argument, and a worked instance.

Lean formalization Intermediate+

Mathlib already supplies the operational definitions and the Bézout identity in the form needed for everyday formalisation, but the pedagogical reconstruction below names the load-bearing pieces explicitly.

-- Operative imports: Mathlib.Data.Int.GCD, Mathlib.Data.Nat.GCD.Basic,
-- Mathlib.RingTheory.EuclideanDomain, Mathlib.RingTheory.PrincipalIdealDomain

#check @Nat.gcd                -- Nat → Nat → Nat
#check @Nat.gcd_dvd_left        -- ∀ (m n : Nat), Nat.gcd m n ∣ m
#check @Nat.gcd_dvd_right       -- ∀ (m n : Nat), Nat.gcd m n ∣ n
#check @Nat.dvd_gcd             -- ∀ {m n k : Nat}, k ∣ m → k ∣ n → k ∣ Nat.gcd m n

-- Bezout via extended Euclidean (xgcd):
#check @Int.gcd_eq_gcd_ab
-- Int.gcd_eq_gcd_ab :
--   ∀ (a b : ℤ), (Int.gcd a b : ℤ) = a * Int.gcdA a b + b * Int.gcdB a b

-- Ring-theoretic generalisation:
#check @EuclideanDomain
#check @IsPrincipalIdealRing
example : IsPrincipalIdealRing ℤ := inferInstance

The unit's central theorem (Bézout's identity in $Z$ ) is Int.gcd_eq_gcd_ab, which Mathlib derives from the recursive Int.xgcd mirroring the algorithm of Exercise 7. The implication EuclideanDomain ⇒ IsPrincipalIdealRing lives in Mathlib.RingTheory.PrincipalIdealDomain and supplies the ring-theoretic abstraction underpinning the Master-tier statement that $Z$ is a PID. What Mathlib does not yet supply in a unified pedagogical module — the Lamé complexity bound, the binary GCD, the Lehmer word-level speedup, and the Knuth-Schönhage half-GCD — is documented in the unit metadata Mathlib gap analysis.

Advanced results Master

Theorem 1 (Bézout's identity, ring-theoretic restatement). The set $Z a + Z b = {a x + b y : x, y \in Z}$ is an ideal of $Z$ , and equals $Z g cd (a, b)$ . Equivalently, the principal ideals satisfy $(a) + (b) = (d)$ with $d = g cd (a, b)$ . This is the ideal-theoretic encoding of Bézout: the gcd is the generator of the ideal sum, and the existence of $x, y$ with $a x + b y = d$ is the statement that $d$ lies in $Z a + Z b$ .

Theorem 2 (Lamé 1844 C.R. Acad. Sci. 19). The number of division steps required by the Euclidean algorithm to compute $g cd (a, b)$ with $a > b > 0$ is at most five times the number of decimal digits of $b$ . Equivalently, the worst-case running time is $O (lo g_{ϕ} b) = O (lo g b)$ , with the worst case realised by consecutive Fibonacci numbers $F_{n + 1}$ and $F_{n}$ . ^{[Lamé 1844]} The constant five comes from the inequality $ϕ^{5} > 10$ , where $ϕ = (1 + 5) /2$ is the golden ratio: each Euclidean step reduces the smaller argument by a factor at least $ϕ$ in the worst case, so the number of steps is bounded by $lo g_{ϕ} b = lo g b / lo g ϕ \approx 4.785 lo g_{10} b$ .

Theorem 3 (Stein 1967 binary GCD). The binary GCD algorithm computes $g cd (a, b)$ using only bit-shifts, subtractions, and tests for parity, avoiding integer division altogether ^{[Stein 1967]}. On a binary computer this is typically 20-60% faster than the Euclidean algorithm despite using more steps, because each step is cheaper. The algorithm uses three rules: $g cd (2 a, 2 b) = 2 g cd (a, b)$ , $g cd (2 a, b) = g cd (a, b)$ for odd $b$ , and $g cd (a, b) = g cd (∣ a - b ∣, b)$ for odd $a, b$ . The bit-complexity is $O (n^{2})$ for $n$ -bit inputs, identical asymptotically to the ordinary Euclidean algorithm but with smaller hidden constants on real hardware. Knuth 1997 §4.5.2 gives the full analysis ^{[Knuth 1997]}.

Theorem 4 (Lehmer 1938 word-level speedup). For multi-precision integers represented as arrays of machine words, the Euclidean algorithm can be sped up by performing several Euclidean steps at the level of the leading words alone, then committing the accumulated $2 \times 2$ matrix back to multi-precision ^{[Lehmer 1938]}. This reduces the number of multi-precision operations by a factor of the machine word size (typically $32$ or $64$ ), at the cost of a small constant overhead per word-level pass. Knuth 1997 §4.5.2 contains the full pseudocode and complexity analysis.

Theorem 5 (Knuth-Schönhage subquadratic GCD). The half-GCD algorithm reduces the computation of $g cd (a, b)$ for $n$ -bit integers $a, b$ to a constant number of $n /2$ -bit multiplications, recursively yielding a complexity $O (M (n) lo g n)$ where $M (n)$ is the cost of $n$ -bit multiplication ^{[Knuth 1997]}. With Schönhage-Strassen-style FFT multiplication at $M (n) = O (n lo g n lo g lo g n)$ , the GCD complexity becomes $O (n (lo g n)^{2} lo g lo g n)$ , beating the quadratic Euclidean bound. The algorithm proceeds by computing a $2 \times 2$ integer matrix that effects $n /2$ Euclidean steps at once.

Theorem 6 (Euclidean domains and the implication chain). Every Euclidean domain is a principal ideal domain, and every PID is a unique factorisation domain. The implications are strict: $Z [(1 + - 19) /2]$ is a PID that is not Euclidean (Motzkin 1949); $Z [- 5]$ is a Noetherian integral domain that is neither PID nor UFD (witnessed by $6 = 2 \times 3 = (1 + - 5) (1 - - 5)$ ). The proof Euclidean $\Rightarrow$ PID is precisely the well-ordering / minimal-positive-element argument we used for $Z$ ; the proof PID $\Rightarrow$ UFD reduces to Euclid's Lemma via the ideal characterisation of primality. Lang 2002 Algebra Ch. II §1 contains the full development ^{[Lang 2002]}.

Theorem 7 (Lattice interpretation; $Z$ as a PID). The set $Z a + Z b$ is the rank-1 sublattice of $Z$ generated by $g cd (a, b)$ . This identifies the action of the $2 \times 2$ integer matrix

(a x_{0} b y_{0}) with det = - g cd (a, b)

with a unimodular transformation of $Z^{2}$ that diagonalises $(a, b)$ to $(d, 0)$ via the Smith normal form. The Smith normal form for general $m \times n$ integer matrices generalises this picture: every integer matrix admits a decomposition $U D V = M$ with $U, V$ unimodular and $D$ diagonal with each diagonal entry dividing the next, recovering the entire elementary-divisor theory of finitely generated abelian groups (a foundational consequence of Theorem 6).

Theorem 8 (Euclid's algorithm in $Z [i]$ ). The Gaussian integers $Z [i] = {a + bi : a, b \in Z}$ form a Euclidean domain under the norm $N (a + bi) = a^{2} + b^{2}$ . The division algorithm: given $α, β \in Z [i]$ with $β \neq = 0$ , write $α / β = u + v i$ with $u, v \in Q$ and let $γ = m + ni$ where $m, n$ are integers closest to $u, v$ respectively. Then $∣ α - γ β ∣^{2} /∣ β ∣^{2} \leq 1/2 < 1$ , so $N (α - γ β) < N (β)$ . The Euclidean recursion terminates on the strictly decreasing norm. Consequence: $Z [i]$ is a PID and a UFD, the foundation of Fermat's two-square theorem ( $p = a^{2} + b^{2}$ iff $p \equiv 1 (mod 4)$ for odd primes $p$ ).

Synthesis. The Euclidean algorithm is the foundational reason that $Z$ is a principal ideal domain, and this is exactly the bridge from elementary number theory to commutative algebra. The central insight is that one effective division-with-remainder operation — once verified to terminate via a well-founded norm — generates the entire ideal-theoretic structure: Bézout's identity, Euclid's Lemma, the fundamental theorem of arithmetic, the structure theorem for finitely generated abelian groups, and the Smith normal form. The pattern generalises from $Z$ to every Euclidean domain ( $k [X]$ for $k$ a field, $Z [i]$ , $Z [ω]$ , the formal power series $k [[X]]$ , the localisation $Z_{(p)}$ at a prime), and the implication Euclidean $\Rightarrow$ PID $\Rightarrow$ UFD identifies the algorithmic content of $Z$ with its categorical-algebraic content.

Putting these together with the complexity analysis, the Euclidean algorithm is one of the rare procedures of antiquity (Euclid c. 300 BCE) that survives without modification into modern algorithmics: Lamé 1844 established the logarithmic step count, Stein 1967 reframed for binary hardware, Lehmer 1938 added the word-level speedup, and Knuth-Schönhage 1971 broke the quadratic bit-complexity barrier via the half-GCD. The bridge is exactly the lattice identification $Z a + Z b = Z g cd (a, b)$ , which generalises into the lattice reduction of Lenstra-Lenstra-Lovász 1982 (LLL), cryptanalytic shortest-vector approximations, and the modern theory of integer linear programming.

Full proof set Master

Proposition 1 (Lamé's bound, full proof). If the Euclidean algorithm on $(a, b)$ with $a > b > 0$ requires exactly $n$ division steps before terminating, then $b \geq F_{n + 1}$ , where $F_{k}$ is the $k$ -th Fibonacci number ( $F_{1} = F_{2} = 1$ ).

Proof. Let $r_{0} = a, r_{1} = b, r_{2}, \dots, r_{n} = g cd (a, b), r_{n + 1} = 0$ be the remainder sequence. We claim by reverse induction on $i \in {0, 1, \dots, n + 1}$ that $r_{n + 1 - i} \geq F_{i}$ .

Base cases: $r_{n + 1} = 0 = F_{0}$ and $r_{n} = g cd (a, b) \geq 1 = F_{1}$ .

Inductive step. Assume $r_{n + 1 - i} \geq F_{i}$ and $r_{n + 2 - i} \geq F_{i - 1}$ . Each Euclidean step satisfies $r_{j - 1} = q_{j} r_{j} + r_{j + 1}$ with $q_{j} \geq 1$ (since the step is non-degenerate). Hence $r_{j - 1} \geq r_{j} + r_{j + 1}$ . Applying this with $j = n + 1 - i$ :

r_{n - i} \geq r_{n + 1 - i} + r_{n + 2 - i} \geq F_{i} + F_{i - 1} = F_{i + 1} .

The induction proceeds. Taking $i = n$ gives $r_{1} = b \geq F_{n + 1}$ . $□$

Corollary. Inverting via the Fibonacci closed form $F_{k} = (ϕ^{k} - ψ^{k}) / 5$ with $ϕ = (1 + 5) /2 \approx 1.618$ and $ψ = (1 - 5) /2 \approx - 0.618$ , the step count satisfies $n + 1 \leq lo g_{ϕ} (b 5) + 1$ , hence $n = O (lo g b)$ . The constant five in Lamé's original statement is the consequence $ϕ^{5} > 10$ : each five steps of the Euclidean algorithm reduce $b$ by at least a factor of $10$ , so the number of steps is at most $5 lo g_{10} (b)$ plus a constant.

Proposition 2 ( $Z$ is a PID, via Bézout). Every ideal $I \subseteq Z$ is principal.

Proof. If $I = {0}$ , then $I = (0)$ is principal. Otherwise let $d$ be the least positive element of $I$ (which exists by well-ordering applied to $I \cap N_{> 0}$ , non-empty because $I$ contains nonzero integers and their negatives). We claim $I = (d)$ .

The inclusion $(d) \subseteq I$ is immediate since $d \in I$ and $I$ is closed under integer multiplication.

For $I \subseteq (d)$ , take any $n \in I$ and divide by $d$ with remainder: $n = q d + r$ with $0 \leq r < d$ . Then $r = n - q d \in I$ (since both $n$ and $q d$ lie in $I$ ). If $r > 0$ , this contradicts the minimality of $d$ in $I \cap N_{> 0}$ . Hence $r = 0$ and $n = q d \in (d)$ . $□$

Proposition 3 (Euclid's Lemma, ideal-theoretic form). Let $p \in Z$ be a prime. Then the ideal $(p)$ is a prime ideal: if $ab \in (p)$ , then $a \in (p)$ or $b \in (p)$ .

Proof. Suppose $ab \in (p)$ , meaning $p ∣ ab$ . If $a \in / (p)$ , then $p ∤ a$ , so $g cd (p, a) = 1$ (since the only positive divisors of the prime $p$ are $1$ and $p$ , and $p$ does not divide $a$ ). By Bézout, $1 = p u + a v$ for some $u, v \in Z$ . Multiply by $b$ : $b = p u b + ab v$ . Both $p u b$ and $ab v$ are divisible by $p$ (the first directly, the second because $p ∣ ab$ ), so $p ∣ b$ , i.e., $b \in (p)$ . $□$

Proposition 4 (Fundamental theorem of arithmetic). Every integer $n \geq 2$ admits a factorisation $n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}}$ as a product of prime powers, unique up to reordering.

Proof. Existence: by strong induction on $n$ (see 00.12.01). If $n$ is prime, the factorisation is $n$ itself. Otherwise $n = ab$ with $2 \leq a, b < n$ , and the inductive hypothesis gives prime factorisations of $a$ and $b$ ; concatenating yields one for $n$ .

Uniqueness: suppose $p_{1} \dots p_{m} = q_{1} \dots q_{ℓ}$ are two prime factorisations of the same integer. By Euclid's Lemma (Proposition 3), $p_{1} ∣ q_{j}$ for some $j$ ; since $q_{j}$ is prime, $p_{1} = q_{j}$ . Cancel and induct on $max (m, ℓ)$ . $□$

Connections Master

Mathematical induction 00.12.01. The termination proof for the Euclidean algorithm reduces to strong induction on the smaller argument, and the proof of Bézout's identity via well-ordering uses the equivalent well-ordering principle established in the induction unit. The lattice-of-ideals argument in Proposition 2 (every ideal of $Z$ is principal) is itself a well-ordering argument on the positive elements of the ideal. The foundational reason these arguments work is that $N$ is well-founded, the load-bearing structural fact catalogued in 00.12.01.
Real numbers, integers, rationals 00.01.01. The integers $Z$ are the substrate on which divisibility, gcd, and Bézout coefficients are defined. The construction of $Z$ from $N$ (via ordered pairs and the equivalence $(a, b) \sim (c, d) ⟺ a + d = b + c$ ) supplies the additive-inverse machinery that lets Bézout coefficients be negative. The construction of $Q$ as a field of fractions then relies on the lemma "every nonzero integer has a gcd with every other nonzero integer", established here as a corollary of Bézout.
Group theory 01.02.01. The set $Z a + Z b = Z g cd (a, b)$ is a cyclic subgroup of $(Z, +)$ , and the lattice interpretation in Theorem 7 generalises to the structure theorem for finitely generated abelian groups: every such group is a direct sum of cyclic factors, with the diagonal entries of the Smith normal form recording the invariant factors. The Bézout argument is the load-bearing step in the rank-1 case, and the Smith-normal-form induction extends it to arbitrary rank. This is the bridge from elementary number theory to the structure theory of modules over a PID.
Hilbert basis theorem 01.02.17. The Noetherian property of $Z$ — every ascending chain of ideals stabilises — is an immediate consequence of $Z$ being a PID, established via Bézout in Proposition 2. The chain $(d_{1}) \subseteq (d_{2}) \subseteq \dots$ of ideals corresponds to a chain $d_{1} ∣ d_{2} ∣ \dots$ of divisibility relations among generators, and the strictly decreasing alternative (in the divisibility order, replacing "less than" with "properly divides") cannot extend indefinitely. The general Hilbert basis theorem catalogued in 01.02.17 specialises to this dimension-1 fact for $Z$ , and the extension to multivariate polynomial rings $k [X_{1}, \dots, X_{n}]$ rests on the same well-foundedness pattern.
Riemann zeta function 21.03.01. The Euler product $ζ (s) = \prod_{p} (1 - p^{- s})^{- 1}$ relies on the fundamental theorem of arithmetic (Proposition 4 above), whose proof reduces to Euclid's Lemma and thence to Bézout's identity. The bridge from elementary number theory to analytic number theory is exactly this: the multiplicative structure of $Z$ — unique factorisation — is what allows the Dirichlet series $\sum 1/ n^{s}$ to factor as a product over primes. Without Bézout, the zeta unit's central Euler-product identity would have no proof. This unit is the load-bearing prerequisite for the entire L-function development in chapter 21.03.

Historical & philosophical context Master

The Euclidean algorithm is among the oldest mathematical procedures still in active use. Euclid c. 300 BCE Elements Book VII Propositions 1-2 ^[Euclid] gives the algorithm for natural numbers — under the name anthyphairesis ( $\overset{α}{˙} ν θ υ ϕ α \overset{ι}{˙} ρε σ ι ς$ ), "alternating subtraction" — and Proposition VII.2 explicitly establishes that the procedure terminates and produces the greatest common measure. The geometric setting was line segments, with the algorithm originally serving as the test for commensurability: two segments are commensurable if and only if their anthyphairesis terminates. The extension to incommensurable segments, where the procedure does not terminate, is the conceptual seed of the continued-fraction expansions of irrational numbers. Historians (Knorr 1975 The Evolution of the Euclidean Elements, Fowler 1999 The Mathematics of Plato's Academy) trace the algorithm further back to Theaetetus and possibly the Pythagorean discovery of incommensurability in the 5th century BCE.

The complexity analysis is comparatively modern. Lamé 1844 C.R. Acad. Sci. 19 ^{[Lamé 1844]} published a one-page note proving that the number of division steps is at most five times the number of decimal digits of the smaller argument, with the worst case attained by consecutive Fibonacci numbers — the first substantive bit-complexity bound for an algorithm in the modern sense, predating the formalisation of complexity theory by more than a century. The connection to the golden ratio $ϕ$ via $ϕ^{5} > 10$ identifies the worst case with the slowest possible decrease, providing both the asymptotic $O (lo g b)$ bound and the sharp constant.

Stein 1967 J. Comput. Phys. 1 ^{[Stein 1967]} reformulated the algorithm for binary computer arithmetic: by replacing division-with-remainder by parity-test, bit-shift, and subtraction, the binary GCD avoids the multi-precision division that dominates the cost of the classical Euclidean algorithm on machine integers. Lehmer 1938 Amer. Math. Monthly 45 ^{[Lehmer 1938]} had earlier proposed performing several Euclidean steps at the level of leading words to reduce the number of multi-precision operations, a technique still used in modern arbitrary-precision libraries (GMP, Magma). Knuth-Schönhage 1971 introduced the half-GCD algorithm reducing GCD to fast multiplication and thereby breaking the quadratic bit-complexity barrier ^{[Knuth 1997]}. Knuth 1997 TAOCP Vol. 2 §4.5.2 collects the algorithmic theory in one place and remains the canonical reference.

The ring-theoretic abstraction took shape in the late 19th century. Dedekind 1871 introduced the notion of an ideal in his supplements to Dirichlet's Vorlesungen über Zahlentheorie, with the explicit motivation of restoring unique factorisation in algebraic number rings where it fails at the element level. Kronecker 1882 J. reine angew. Math. 92 developed parallel notions via divisors. Noether 1921 Math. Ann. 83 abstracted the chain condition and identified Noetherian rings as the natural setting for unique-factorisation theorems. The chain Euclidean $\Rightarrow$ PID $\Rightarrow$ UFD became standard textbook material with van der Waerden 1930 Moderne Algebra and Lang 2002 Algebra Ch. II §1 ^{[Lang 2002]}. The recognition that $Z$ is the prototype of every PID, and that Bézout's identity is the operational content of the principality, organises modern commutative algebra from its first pages.

Bibliography Master

@book{EuclidElements,
  author    = {Euclid},
  title     = {The Thirteen Books of Euclid's Elements},
  editor    = {Heath, Thomas L.},
  publisher = {Cambridge University Press},
  year      = {1908},
  note      = {Three volumes; Dover reprint 1956. Book VII Propositions 1-2 contain the Euclidean algorithm (anthyphairesis), originally c. 300 BCE}
}

@article{Lame1844,
  author  = {Lam\'{e}, Gabriel},
  title   = {Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers},
  journal = {Comptes Rendus de l'Acad\'{e}mie des Sciences (Paris)},
  volume  = {19},
  pages   = {867--870},
  year    = {1844}
}

@article{Stein1967,
  author  = {Stein, Josef},
  title   = {Computational problems associated with Racah algebra},
  journal = {Journal of Computational Physics},
  volume  = {1},
  pages   = {397--405},
  year    = {1967}
}

@article{Lehmer1938,
  author  = {Lehmer, Derrick Henry},
  title   = {Euclid's algorithm for large numbers},
  journal = {American Mathematical Monthly},
  volume  = {45},
  pages   = {227--233},
  year    = {1938}
}

@book{Knuth1997,
  author    = {Knuth, Donald E.},
  title     = {The Art of Computer Programming, Vol. 2: Seminumerical Algorithms},
  edition   = {3},
  publisher = {Addison-Wesley},
  year      = {1997},
  note      = {Section 4.5.2 (Greatest Common Divisor) is the canonical algorithmic reference}
}

@book{HardyWright2008,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman, foreword by A. Wiles. Chapters I-II contain the elementary theory.}
}

@book{IrelandRosen1990,
  author    = {Ireland, Kenneth and Rosen, Michael},
  title     = {A Classical Introduction to Modern Number Theory},
  edition   = {2},
  series    = {Graduate Texts in Mathematics},
  volume    = {84},
  publisher = {Springer},
  year      = {1990}
}

@book{Lang2002,
  author    = {Lang, Serge},
  title     = {Algebra},
  edition   = {3},
  series    = {Graduate Texts in Mathematics},
  volume    = {211},
  publisher = {Springer},
  year      = {2002},
  note      = {Chapter II §1 develops Euclidean domains, PIDs, and the structure of finitely generated modules over a PID}
}

@book{Apostol1976,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer},
  year      = {1976}
}

Prerequisites

00.01.01
00.12.01

Tier anchors

beginner: Burton 2010 *Elementary Number Theory* 7e §2 (divisibility, gcd, Euclidean algorithm); Khan Academy modular arithmetic introduction
intermediate: Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* (Springer GTM 84, 2e) §1; Apostol 1976 *Introduction to Analytic Number Theory* §1; Niven-Zuckerman-Montgomery 1991 *An Introduction to the Theory of Numbers* 5e Ch. 1
master: Euclid c. 300 BCE *Elements* Book VII Props. 1-2 (originator of the algorithm); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e (Oxford, revised Heath-Brown-Silverman-Wiles) §§I-II; Lang 2002 *Algebra* (Springer GTM 211, 3e) Ch. II §1 (Euclidean rings and principal ideal domains); Knuth 1997 *The Art of Computer Programming, Vol. 2: Seminumerical Algorithms* 3e §4.5.2 (greatest common divisor); Lamé 1844 *Comptes Rendus* 19 (Fibonacci worst case); Stein 1967 *J. Comput. Phys.* 1 (binary GCD)

References

Euclid — Elements, Book VII · Propositions 1-2 (antanairesis, c. 300 BCE). Heath translation, *The Thirteen Books of Euclid's Elements*, Vol. 2, Cambridge University Press 1908; Dover reprint 1956. The earliest extant systematic formulation of the Euclidean algorithm (anthyphairesis, ἀνθυφαίρεσις), originally stated for line segments and applied to commensurability.
Lamé, G. — Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers · *Comptes Rendus de l'Académie des Sciences (Paris)* 19 (1844), 867-870. The first complexity bound for the Euclidean algorithm: the number of division steps required to compute $\gcd(a, b)$ with $a > b > 0$ is at most five times the number of decimal digits of $b$; the worst case is realised by consecutive Fibonacci numbers.
Stein, J. — Computational problems associated with Racah algebra · *Journal of Computational Physics* 1 (1967), 397-405. The binary GCD algorithm replacing trial division with bit-shifts and subtractions, suited to binary computer arithmetic. Analysed in detail in Knuth 1997 §4.5.2.
Knuth, D. E. — The Art of Computer Programming, Vol. 2: Seminumerical Algorithms · Addison-Wesley, 3rd edition (1997), §4.5.2 (Greatest Common Divisor). The canonical algorithmic-analysis reference: Euclidean algorithm complexity, binary GCD, Lehmer 1938 word-level extension, extended Euclidean algorithm for modular inverses, Knuth-Schönhage subquadratic half-GCD.
Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman with a foreword by A. Wiles. §§I-II (divisibility, the Euclidean algorithm, the fundamental theorem of arithmetic via Bézout); the canonical undergraduate reference.
Ireland, K. & Rosen, M. — A Classical Introduction to Modern Number Theory · Springer Graduate Texts in Mathematics 84, 2nd edition (1990). §1 (divisibility, primes, the Euclidean algorithm, the fundamental theorem); the gateway from elementary to algebraic number theory.
Lang, S. — Algebra · Springer Graduate Texts in Mathematics 211, 3rd edition (2002), Ch. II §1. The ring-theoretic framing: Euclidean domains, principal ideal domains, the implication Euclidean ⇒ PID ⇒ UFD, and the structure theorem for finitely generated modules over a PID.
Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics (1976), §1. The arithmetic-function framing of divisibility and gcd, with the Möbius and Euler functions later in the chapter.
Lehmer, D. H. — Euclid's algorithm for large numbers · *American Mathematical Monthly* 45 (1938), 227-233. The word-level Euclidean speedup that performs the leading-digit quotient steps in machine arithmetic before reverting to multi-precision.
Knuth-Schönhage — Subquadratic GCD via half-GCD · Knuth 1971 *J. ACM* 18 (1971), 595-616 and Schönhage 1971 *Acta Inform.* 1 (1971), 139-144. The half-GCD algorithm reducing GCD computation to fast multiplication, giving complexity $O(M(n) \log n)$ for $n$-bit inputs.

Estimated time

beginner: 15m
intermediate: 35m
master: 75m