Divisibility, gcd, and Euclidean algorithm - Discrete Math

SECTION 1

Historical Context & Motivation

The concept of one integer dividing another is arguably the oldest mathematical abstraction, predating even the notion of irrational numbers. Ancient civilizations needed to partition harvests, distribute resources equally, and measure land — all tasks that reduce to questions of divisibility. The Babylonians exploited the rich divisor structure of 60 (divisible by 2, 3, 4, 5, 6, 10, 12, 15, 20, and 30) when they chose their base-60 numeral system, and the Egyptians developed unit-fraction representations that implicitly relied on greatest common divisors. Yet it was the Greeks who first elevated these practical observations into a rigorous mathematical theory, establishing results that remain central to modern algebra, computer science, and cryptography.

c. 300 BCE • Euclid's Elements

In Books VII–IX, Euclid formalizes divisibility, introduces the Euclidean algorithm (Proposition VII.2) for computing the greatest common measure of two lengths, and proves the infinitude of primes.

1801 • Gauss's Disquisitiones Arithmeticae

Carl Friedrich Gauss systematizes modular arithmetic and proves the fundamental theorem of arithmetic (unique prime factorization), placing divisibility at the core of modern number theory.

1844 • Bézout's Identity Generalized

Building on earlier work by Étienne Bézout, mathematicians establish that gcd(a, b) can always be expressed as a linear combination ax + by, providing the algebraic backbone for modular inverses.

1977 • RSA Cryptosystem

Rivest, Shamir, and Adleman publish the RSA algorithm, which relies on the Extended Euclidean Algorithm to compute modular inverses for public-key cryptography — bringing ancient number theory into the digital age.

The persistent question underlying this topic is deceptively simple: given two integers a and b, what is the largest integer that divides both of them, and how can we compute it efficiently? As we will see, the answer involves an elegant recursive reduction — the Euclidean algorithm — whose worst-case running time is logarithmic in the smaller input, making it one of the most efficient algorithms ever devised. Understanding this machinery is prerequisite to studying modular arithmetic, RSA encryption, lattice-based cryptography, and the algebraic structure of ℤ.

SECTION 2

Core Principles & Definitions

Before diving into algorithms, we must establish the formal definitions that govern divisibility and greatest common divisors. These definitions are stated over the integers ℤ, and they form the axiomatic basis for all subsequent results. Every theorem in this lesson rests on the Division Algorithm — which, despite its name, is actually an existence-and-uniqueness theorem rather than a computational procedure.

Divisibility

An integer a divides b (written a ∣ b) if there exists an integer k such that b = a × k. We say a is a divisor or factor of b, and b is a multiple of a.

Division Algorithm

For any integers a and d with d > 0, there exist unique integers q (quotient) and r (remainder) such that a = d × q + r, where 0 ≤ r < d. This guarantees a well-defined remainder operation.

Greatest Common Divisor (gcd)

The gcd of integers a and b (not both zero) is the largest positive integer d such that d ∣ a and d ∣ b. Equivalently, gcd(a, b) is the smallest positive element of the ideal aℤ + bℤ.

Coprimality

Two integers a and b are coprime (or relatively prime) if gcd(a, b) = 1. This condition is central to modular inverses: a has an inverse modulo n if and only if gcd(a, n) = 1.

Bézout's Identity

For any integers a and b, there exist integers x and y (the Bézout coefficients) such that gcd(a, b) = a × x + b × y. These coefficients are computed by the Extended Euclidean Algorithm.

✦

KEY TAKEAWAY

Think of the gcd as a 'greatest common measuring stick.' If you have two rods of lengths 12 cm and 18 cm, the largest ruler that can measure both exactly — without leftover fractions — has length gcd(12, 18) = 6 cm. The Euclidean algorithm finds that ruler by repeatedly subtracting (or, more efficiently, dividing) the longer rod by the shorter one until nothing remains, much like an engineer calibrating precision instruments by iterative comparison.

SECTION 3

Visual Explanation: The Euclidean Algorithm in Action

The Euclidean algorithm computes gcd(a, b) by repeatedly applying the Division Algorithm. At each step, we replace the pair (a, b) with (b, a mod b), and the process terminates when the remainder reaches zero. The last nonzero remainder is the gcd. The following diagram traces gcd(252, 105) through each iteration, showing how the pair of values shrinks until the answer emerges.

Each step applies the Division Algorithm: the divisor becomes the new dividend and the remainder becomes the new divisor. The circled values on the right track the remainder at each iteration. When the remainder reaches 0, the previous remainder (21) is the gcd.

Observe the key invariant: at every step, gcd(a, b) = gcd(b, a mod b). This is because any common divisor of a and b also divides a − q × b = r, and conversely any common divisor of b and r also divides a = q × b + r. The pair's gcd is therefore unchanged across iterations, and termination is guaranteed because the remainder sequence is strictly decreasing and bounded below by 0. In fact, the number of steps is at most 2 × log₂(min(a, b)) + 1, which can be tightened to roughly 5 × (number of decimal digits of min(a, b)) — a result tied to the Fibonacci numbers being the worst-case inputs.

SECTION 4

Mathematical Framework

We now formalize the key results. The mathematical framework comprises the Division Algorithm (the engine), the Euclidean algorithm (the procedure), Bézout's Identity (the linear-combination guarantee), and the Extended Euclidean Algorithm (the procedure that computes Bézout coefficients alongside the gcd).

DIVISION ALGORITHM

a = d × q + r, 0 ≤ r < d

For integers a ∈ ℤ and d ∈ ℤ⁺, there exist unique integers q (quotient) and r (remainder) satisfying this equation. Uniqueness is proven by assuming two representations and showing both lead to the same q and r.

EUCLIDEAN ALGORITHM RECURRENCE

gcd(a, b) = gcd(b, a mod b), gcd(a, 0) = a

This recurrence follows from the fact that the set of common divisors of a and b equals the set of common divisors of b and (a mod b). The base case gcd(a, 0) = a holds because every integer divides 0.

BÉZOUT'S IDENTITY

gcd(a, b) = a × x + b × y

There exist integers x, y ∈ ℤ (Bézout coefficients) satisfying this equation. Proof: the set S = {a × m + b × n > 0 : m, n ∈ ℤ} is nonempty (since |a| or |b| ∈ S). Let d be the smallest element of S. By the Division Algorithm, d divides both a and b, and one can show d = gcd(a, b).

WORST-CASE COMPLEXITY (LAMÉ'S THEOREM)

Steps ≤ 5 × log₁₀(min(a, b))

Gabriel Lamé proved in 1844 that the Euclidean algorithm on inputs a > b > 0 terminates in at most 5k steps, where k is the number of decimal digits of b. The worst case occurs when the inputs are consecutive Fibonacci numbers, since the quotient at every step is 1 — yielding the slowest possible remainder reduction.

ℹ

Why does this matter for cryptography?

In RSA, we need to compute the modular inverse of the public exponent e modulo φ(n). This inverse exists precisely when gcd(e, φ(n)) = 1 (coprimality), and it is computed via the Extended Euclidean Algorithm, which back-substitutes through the recurrence to extract the Bézout coefficients x and y. The coefficient x (reduced modulo φ(n)) is the private decryption exponent d.

SECTION 5

The Extended Euclidean Algorithm

The standard Euclidean algorithm tells us the gcd, but many applications — particularly computing modular inverses — require the Bézout coefficients as well. The Extended Euclidean Algorithm (EEA) augments each step with bookkeeping that tracks how the current remainder can be expressed as a linear combination of the original inputs a and b. By the time the remainder reaches zero, the coefficients for the last nonzero remainder give us gcd(a, b) = a × x + b × y directly.

The table tracks three parallel sequences: remainders rᵢ (blue), and Bézout coefficients sᵢ (green) and tᵢ (pink). Each row applies the same quotient qᵢ (amber) to update all three sequences simultaneously. The Bézout coefficients from the row where the last nonzero remainder appears give the desired x and y.

The update rules are elegantly simple: at each step i ≥ 2, we compute qᵢ = ⌊rᵢ₋₂ / rᵢ₋₁⌋, then update rᵢ = rᵢ₋₂ − qᵢ × rᵢ₋₁, and apply the identical formula to both coefficient sequences. The invariant maintained at every step is rᵢ = a × sᵢ + b × tᵢ. When rᵢ = 0, the previous row's sᵢ₋₁ and tᵢ₋₁ are exactly the Bézout coefficients x and y. This procedure runs in the same O(log(min(a, b))) time as the standard algorithm, since it merely adds two extra multiplications and subtractions per iteration.

SECTION 6

Worked Example: Computing gcd and Bézout Coefficients

Let us compute gcd(1914, 899) using the Euclidean algorithm, then back-substitute to find the Bézout coefficients. This example demonstrates a case with more iterations and non-trivial coefficients.

Find gcd(1914, 899) and express it as 1914x + 899y

1
Step 1 — Apply the Division Algorithm

Divide 1914 by 899: we get 1914 = 899 × 2 + 116. The quotient is 2 and the remainder is 116. So gcd(1914, 899) = gcd(899, 116).

r₁ = 116, q₁ = 2
2
Step 2 — Continue the recursion

Divide 899 by 116: we get 899 = 116 × 7 + 87. The pair becomes (116, 87).

r₂ = 87, q₂ = 7
3
Step 3 — Next iteration

Divide 116 by 87: we get 116 = 87 × 1 + 29. The pair becomes (87, 29).

r₃ = 29, q₃ = 1
4
Step 4 — Final division

Divide 87 by 29: we get 87 = 29 × 3 + 0. The remainder is 0, so the algorithm terminates. The last nonzero remainder is 29.

gcd(1914, 899) = 29
5
Step 5 — Back-substitute for Bézout coefficients

From Step 3: 29 = 116 − 87 × 1. From Step 2: 87 = 899 − 116 × 7, so substitute: 29 = 116 − (899 − 116 × 7) = 116 × 8 − 899. From Step 1: 116 = 1914 − 899 × 2, so substitute: 29 = (1914 − 899 × 2) × 8 − 899 = 1914 × 8 − 899 × 16 − 899 = 1914 × 8 − 899 × 17.

29 = 1914 × 8 + 899 × (−17) → x = 8, y = −17
6
Step 6 — Verify

Check: 1914 × 8 = 15312 and 899 × 17 = 15283. So 15312 − 15283 = 29. ✓ Also verify 1914 / 29 = 66 and 899 / 29 = 31, confirming 29 divides both.

Verified: gcd(1914, 899) = 29 = 1914(8) + 899(−17) ✓

SECTION 7

Methods for Computing gcd: Strengths & Limitations

The Euclidean algorithm is not the only way to compute the gcd — prime factorization and the binary GCD algorithm are alternatives. Each method has distinct trade-offs in terms of computational complexity, hardware friendliness, and conceptual clarity. The following table compares the three primary approaches.

Method	Time Complexity	Strengths	Limitations
Prime Factorization	Depends on factoring — typically O(√n) trial division; sub-exponential for general integers	Conceptually intuitive; directly reveals the full prime structure of both numbers	Factoring large integers is computationally hard (this hardness underpins RSA); impractical for numbers with hundreds of digits
Euclidean Algorithm	O(log(min(a, b))) divisions	Extremely efficient; does not require factoring; naturally extends to Bézout coefficients; works over Euclidean domains	Division operations can be expensive for very large multi-precision integers (each division costs O(n²) for n-digit numbers)
Binary GCD (Stein's)	O(log(max(a, b))²) bit operations	Replaces division with bit shifts and subtraction — faster on hardware; avoids costly multi-precision division	Does not directly produce Bézout coefficients; more complex to implement; advantages vanish for small inputs

Comparison of gcd computation methods

✦

KEY TAKEAWAY

The Euclidean algorithm occupies a sweet spot: it is fast enough for virtually all practical purposes (including thousand-digit cryptographic keys), produces the Bézout coefficients needed for modular inverses, generalizes to polynomials and other Euclidean domains, and is simple enough to implement in a few lines of code. For hardware-level optimizations in specialized chips, the binary GCD can offer a constant-factor speedup, but the Euclidean algorithm remains the standard choice in software implementations.

SECTION 8

Connection to Advanced Theory

The concepts of divisibility and gcd are not confined to ℤ — they generalize to any Euclidean domain, an algebraic structure equipped with a norm function that allows a Division Algorithm. Polynomial rings like F[x] over a field F are the most important example: the Euclidean algorithm applied to polynomials is used in error-correcting codes (Reed-Solomon), symbolic computation, and the theory of finite fields. The table below highlights how the integer-level theory scales up.

Concept in ℤ	Generalization	Application
gcd(a, b) ∈ ℤ	gcd(f(x), g(x)) ∈ F[x] computed by polynomial Euclidean algorithm	Reed-Solomon error-correcting codes; simplifying rational expressions
Bézout's Identity: ax + by = gcd	Bézout's Identity in principal ideal domains (PIDs)	Chinese Remainder Theorem; solving systems of congruences
Modular inverse via Extended Euclidean	Inversion in ℤ/nℤ* and in F[x]/(p(x))	RSA decryption key; AES field arithmetic in GF(2⁸)
Unique prime factorization in ℤ	Unique factorization in UFDs	Algebraic number theory; class group computation

From integers to general algebraic structures

Beyond algebra, continued fractions provide a beautiful reinterpretation of the Euclidean algorithm: the sequence of quotients q₁, q₂, … produced during gcd(a, b) are precisely the partial quotients in the continued fraction expansion of a/b. This connection leads to optimal rational approximations (convergents) and has deep ties to Diophantine approximation, dynamical systems, and even quantum computing (where continued fractions appear in Shor's algorithm for period-finding).

💡

Looking Ahead

Once you are comfortable with the Euclidean algorithm, the natural next topics are modular arithmetic (building ℤ/nℤ), the Chinese Remainder Theorem (decomposing ℤ/nℤ when n is composite), and Euler's theorem (generalizing Fermat's little theorem). These form the algebraic core of RSA, Diffie-Hellman, and elliptic curve cryptography.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why gcd(a, 0) = a for any positive integer a. How does this serve as the base case for the Euclidean algorithm, and what would go wrong if we did not define it this way?

Show answer

Every integer divides 0, because 0 = a × 0 for any a. Therefore the set of common divisors of a and 0 is exactly the set of divisors of a, and the greatest among these is a itself. This base case is essential because the Euclidean algorithm repeatedly reduces the pair (a, b) to (b, a mod b); eventually the smaller entry reaches 0, and the algorithm must return a definite answer at that point. Without the convention gcd(a, 0) = a, the recursion would have no well-defined termination value, and the entire algorithm would fail to produce output.

Question 2: BASIC CALCULATION

Use the Euclidean algorithm to compute gcd(468, 126). Show each step of the division.

Show answer

Step 1: 468 = 126 × 3 + 90. Step 2: 126 = 90 × 1 + 36. Step 3: 90 = 36 × 2 + 18. Step 4: 36 = 18 × 2 + 0. The last nonzero remainder is 18, so gcd(468, 126) = 18. We can verify: 468 / 18 = 26 and 126 / 18 = 7, and gcd(26, 7) = 1, confirming that 18 is indeed the greatest common divisor.

Question 3: INTERMEDIATE

Use the Extended Euclidean Algorithm to find integers x and y such that 1914x + 899y = gcd(1914, 899). Verify your answer.

Show answer

First compute gcd(1914, 899) via the Euclidean algorithm: 1914 = 899 × 2 + 116; 899 = 116 × 7 + 87; 116 = 87 × 1 + 29; 87 = 29 × 3 + 0. So gcd = 29. Now back-substitute: 29 = 116 − 87 × 1 = 116 − (899 − 116 × 7) = 116 × 8 − 899 = (1914 − 899 × 2) × 8 − 899 = 1914 × 8 − 899 × 17. Therefore x = 8 and y = −17. Verification: 1914 × 8 = 15312, and 899 × 17 = 15283, so 15312 − 15283 = 29. ✓

Question 4: APPLIED

In a simplified RSA setup, let p = 11, q = 13, so n = 143 and φ(n) = 120. The public exponent is e = 7. Use the Extended Euclidean Algorithm to find the private exponent d (the inverse of e modulo 120). Verify that e × d ≡ 1 (mod 120).

Show answer

We need d such that 7d ≡ 1 (mod 120), i.e., we need gcd(7, 120) = 1 and the Bézout coefficient for 7. Apply the algorithm: 120 = 7 × 17 + 1; 7 = 1 × 7 + 0. So gcd(7, 120) = 1, confirming the inverse exists. From the first equation: 1 = 120 − 7 × 17, so 1 = 120 × 1 + 7 × (−17). The Bézout coefficient for 7 is −17. Reducing modulo 120: d = −17 mod 120 = 103. Verification: 7 × 103 = 721 = 6 × 120 + 1, so 721 ≡ 1 (mod 120). ✓ The private key exponent is d = 103.

Question 5: CRITICAL THINKING

Prove that consecutive Fibonacci numbers Fₙ and Fₙ₊₁ are always coprime (i.e., gcd(Fₙ, Fₙ₊₁) = 1 for all n ≥ 1). Then explain why the Euclidean algorithm takes the maximum number of steps when applied to consecutive Fibonacci numbers.

Show answer

Proof by induction. Base case: gcd(F₁, F₂) = gcd(1, 1) = 1. Inductive step: assume gcd(Fₙ, Fₙ₊₁) = 1. Since Fₙ₊₂ = Fₙ₊₁ + Fₙ, any common divisor d of Fₙ₊₁ and Fₙ₊₂ must also divide Fₙ₊₂ − Fₙ₊₁ = Fₙ. But then d divides both Fₙ and Fₙ₊₁, so d = 1 by the inductive hypothesis. Hence gcd(Fₙ₊₁, Fₙ₊₂) = 1. For the second part: when we apply the Euclidean algorithm to (Fₙ₊₁, Fₙ), we get Fₙ₊₁ = Fₙ × 1 + Fₙ₋₁, so the quotient is always 1 — the smallest possible value that still reduces the remainder. This means the remainder decreases as slowly as possible at every step, requiring n − 1 iterations to reach gcd = 1. This is precisely the worst case identified in Lamé's theorem.

SUMMARY

Lesson Summary

Summary

This lesson established the foundational number-theoretic concepts of divisibility (a ∣ b when b = ak for some integer k), the Division Algorithm (existence and uniqueness of quotient and remainder), and the greatest common divisor (the largest integer dividing two given integers). The Euclidean algorithm computes the gcd via the recurrence gcd(a, b) = gcd(b, a mod b), terminating in O(log(min(a, b))) steps — a result formalized by Lamé's theorem, with consecutive Fibonacci numbers providing the worst-case inputs.

The Extended Euclidean Algorithm augments the standard algorithm to produce Bézout coefficients x and y satisfying gcd(a, b) = ax + by, which is essential for computing modular inverses in cryptographic protocols like RSA. The theory generalizes beyond ℤ to polynomial rings and Euclidean domains, underpinning error-correcting codes, finite field arithmetic, and modern algebraic cryptography. Mastery of these concepts is prerequisite for studying modular arithmetic, the Chinese Remainder Theorem, and public-key cryptosystems.