Divisibility, GCD, and the Euclidean Algorithm

One-line statement: For integers

a, b

(not both zero), the greatest common divisor

g cd (a, b)

is the largest positive integer dividing both, and the Euclidean Algorithm computes it via repeated division with remainder. Key result in words:

g cd (a, b)

can be expressed as an integer linear combination

a x + b y

(Bézout's identity), and the Euclidean Algorithm finds it in

O (lo g min (∣ a ∣, ∣ b ∣))

division steps. Where it applies: number theory, cryptography (RSA, modular inverses), abstract algebra (PIDs, ideals), computer algebra, rational arithmetic. Who/when: Euclid (~300 BCE, Elements Book VII); formalized over millennia into modern number theory.

A nonzero integer $d$ divides an integer $a$ , written $d ∣ a$ , if $a = d q$ for some integer $q$ . The greatest common divisor of two integers $a, b$ (not both zero) is the unique largest positive integer that divides both. The Euclidean Algorithm exploits the invariance of the gcd under subtraction of multiples — $g cd (a, b) = g cd (b, a mod b)$ — to reduce the problem rapidly to a base case. The surprising and deeply consequential fact is Bézout's identity: the gcd is always expressible as $a x + b y$ for integers $x, y$ , which makes the gcd not just a number but a generator of an ideal. This single algorithm underlies modular inverses, the structure of $Z / n Z$ , and the entire edifice of public-key cryptography.

The Core Insight

If $d$ divides both $a$ and $b$ , then $d$ divides every integer combination $a x + b y$ . In particular $d$ divides $a - q b$ for any integer $q$ . Therefore the set of common divisors of $(a, b)$ equals the set of common divisors of $(b, a - q b)$ . Choosing $q = ⌊ a / b ⌋$ replaces $a$ with the remainder $r = a mod b$ , which is strictly smaller. Iterating shrinks the numbers until the remainder is $0$ — and the last nonzero remainder is the gcd. The gcd is preserved at every step; only the representation gets simpler.

Formal Statement

Divisibility

For integers $a, d$ with $d \neq = 0$ , we say $d$ divides $a$ (equivalently $d$ is a divisor of $a$ , or $a$ is a multiple of $d$ ), written $d ∣ a$ , if there exists an integer $q$ with:

a = d q, q \in Z .

⟳this is a definition;

q

is the quotient. Note

d ∣ 0

for every nonzero

d

, since

0 = d \cdot 0

Basic properties (for nonzero divisors where needed): $d ∣ a$ and $d ∣ b$ imply $d ∣ (a \pm b)$ ; $d ∣ a$ implies $d ∣ k a$ for all $k$ ; divisibility is transitive ( $d ∣ a$ , $a ∣ b \Rightarrow d ∣ b$ ); and $d ∣ a$ with $a \neq = 0$ forces $∣ d ∣ \leq ∣ a ∣$ .

Division Algorithm

For any integers $a$ and $b$ with $b > 0$ , there exist unique integers $q$ (quotient) and $r$ (remainder) such that:

a = b q + r, 0 \leq r < b .

⟳existence by taking

q = ⌊ a / b ⌋

so that

r = a - b q \in [0, b)

; uniqueness by assuming two representations and bounding their difference below

b

Greatest Common Divisor

For integers $a, b$ not both zero, the greatest common divisor $g cd (a, b)$ is the unique positive integer $d$ satisfying:

d ∣ a, d ∣ b, and (c ∣ a and c ∣ b ⟹ c ∣ d) .

⟳the third clause (every common divisor divides

d

) is stronger than mere maximality in size; it characterizes the gcd up to sign and is the form that generalizes to rings.

By convention $g cd (a, 0) = ∣ a ∣$ for $a \neq = 0$ , and $g cd (0, 0)$ is undefined (or set to $0$ ). Integers $a, b$ are coprime (relatively prime) when $g cd (a, b) = 1$ .

Bézout's Identity

For integers $a, b$ not both zero, there exist integers $x, y$ such that:

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

⟳let

d

be the smallest positive value of

{a x + b y : x, y \in Z}

; show

d ∣ a

and

d ∣ b

via the division algorithm (a smaller positive remainder would contradict minimality), and that any common divisor divides

d

Equivalently, $g cd (a, b)$ is the smallest positive element of the set ${a x + b y}$ , and that set is exactly the set of all multiples of $g cd (a, b)$ — i.e. the ideal $(a, b) = (g cd (a, b))$ in $Z$ .

Key Reduction Lemma

For integers $a, b$ with $b \neq = 0$ and $a = b q + r$ :

g cd (a, b) = g cd (b, r) = g cd (b, a mod b) .

⟳show the common-divisor sets of

(a, b)

and

(b, r)

coincide. If

c ∣ a

and

c ∣ b

then

c ∣ (a - b q) = r

; conversely if

c ∣ b

and

c ∣ r

then

c ∣ (b q + r) = a

Why It Holds / Derivation

Correctness and Termination of the Euclidean Algorithm

We prove the algorithm $g cd (a, b)$ — assume WLOG $a \geq b > 0$ — computes the gcd and halts.

Step 1 — Setup. Define

r_{0} = a

r_{1} = b

. Repeatedly apply the division algorithm:

r_{k - 1} = r_{k} q_{k} + r_{k + 1}, 0 \leq r_{k + 1} < r_{k} .

⟳each line is one application of [2] with divisor

r_{k} > 0

, producing remainder

r_{k + 1}

Step 2 — Termination. The remainders form a strictly decreasing sequence of nonnegative integers

r_{1} > r_{2} > r_{3} > \dots \geq 0

. A strictly decreasing sequence of nonnegative integers must reach

0

in finitely many steps. Let

r_{n + 1} = 0

be the first zero remainder; then

r_{n}

is the last nonzero remainder. Step 3 — Invariance. By [5], each division step preserves the gcd:

g cd (r_{k - 1}, r_{k}) = g cd (r_{k}, r_{k + 1}) .

⟳direct application of the Key Reduction Lemma to line [6].

Step 4 — Chaining. Composing [7] from

k = 1

up through

k = n

g cd (a, b) = g cd (r_{0}, r_{1}) = g cd (r_{1}, r_{2}) = \dots = g cd (r_{n}, r_{n + 1}) = g cd (r_{n}, 0) = r_{n} .

⟳telescope the chain of equalities; the final term uses

g cd (d, 0) = d

Hence the algorithm returns $r_{n} = g cd (a, b)$ . $■$

Complexity. Each two consecutive remainders satisfy

r_{k + 2} < r_{k} /2

(since either

r_{k + 1} \leq r_{k} /2

already, or

r_{k + 1} > r_{k} /2

forcing

q_{k + 1} = 1

and

r_{k + 2} = r_{k} - r_{k + 1} < r_{k} /2

). Thus the number of steps is

O (lo g_{2} min (a, b))

. The worst case occurs for consecutive Fibonacci numbers (Lamé's theorem), giving roughly

lo g_{φ}

steps where

φ

is the golden ratio.

One pass of the Euclidean Algorithm on gcd(48, 18) = 6

Euclid of Alexandria | fl. ~300 BCE

Euclid, working at the Library of Alexandria, presented the algorithm now bearing his name in the Elements, Propositions VII.1–VII.2, originally phrased for "magnitudes" via repeated subtraction (anthyphairesis, "reciprocal subtraction"). His version applied both to integers and to commensurable geometric lengths; if the subtraction never terminates, the magnitudes are incommensurable — the same idea that proves $2$ irrational. The algorithm is among the oldest still in everyday computational use, and the ideal-theoretic generalization (gcd as ideal generator) flows directly from his proof structure.

Building Intuition

Picture two rulers of integer lengths $a$ and $b$ laid end-to-end measuring problems. The gcd is the length of the largest "tile" that can pave both rulers exactly with no gap. The Euclidean Algorithm tiles the long ruler with copies of the short one, then re-tiles the leftover strip with copies of it, and so on — the leftover that finally tiles perfectly is the answer. Geometrically: draw an $a \times b$ rectangle, repeatedly cut off the largest possible square; the side of the smallest square you can cut equals $g cd (a, b)$ . Bézout's identity then says: among all combinations $a x + b y$ you can build with signed copies of the two rulers, the shortest nonzero length you can reach is exactly the gcd — you can never reach anything shorter, and you can reach every multiple of it.

Worked Examples

Plain Euclidean Algorithm: gcd(1071, 462)

Given:

a = 1071

b = 462

. Steps (each line is

r_{k - 1} = r_{k} q_{k} + r_{k + 1}

1071462147 = 462 \cdot 2 + 147 = 147 \cdot 3 + 21 = 21 \cdot 7 + 0

⟳apply [2] each line; last nonzero remainder is the gcd.

The last nonzero remainder is $21$ .

g cd (1071, 462) = 21

Check:

1071 = 21 \cdot 51

and

462 = 21 \cdot 22

, and

g cd (51, 22) = 1

. ✓

Extended Euclidean Algorithm: Bézout coefficients & a modular inverse

Given: find

x, y

with

240 x + 46 y = g cd (240, 46)

, then compute

4 6^{- 1} mod 240

if it exists. Forward pass:

240461064 = 46 \cdot 5 + 10 = 10 \cdot 4 + 6 = 6 \cdot 1 + 4 = 4 \cdot 1 + 2 = 2 \cdot 2 + 0

⟳standard division chain; gcd is the last nonzero remainder,

2

So $g cd (240, 46) = 2$ .

Back-substitution (express

2

as a combination):

2 = 6 - 4 \cdot 1 = 6 - (10 - 6 \cdot 1) = 2 \cdot 6 - 10 = 2 (46 - 10 \cdot 4) - 10 = 2 \cdot 46 - 9 \cdot 10 = 2 \cdot 46 - 9 (240 - 46 \cdot 5) = 47 \cdot 46 - 9 \cdot 240.

⟳substitute each remainder from the bottom of [10] upward, collecting coefficients of the two original numbers.

240 \cdot (- 9) + 46 \cdot 47 = 2 = g cd (240, 46)

Modular inverse? Since

g cd (46, 240) = 2 \neq = 1

46

has no inverse mod 240 — the congruence

46 t \equiv 1 (mod 240)

is unsolvable. (An inverse exists iff the numbers are coprime.) However,

46 \cdot 47 \equiv 2 (mod 240)

, so

47

is a "half-inverse." For contrast:

g cd (47, 240) = 1

, and the same method gives

4 7^{- 1} \equiv 23 (mod 240)

since

47 \cdot 23 = 1081 = 4 \cdot 240 + 1

Common Misconceptions

"Greatest" means largest in magnitude — and that's the whole definition. Not quite. The defining property [3] is that the gcd is divisible-into by every common divisor, not merely larger than them. These coincide in

Z

, but in general rings (e.g. polynomial rings) "largest" has no meaning while the divisibility characterization still works. Also beware:

g cd (a, b) ∣ (a x + b y)

for all

x, y

, but

a x + b y

equals the gcd only for special

x, y

— Bézout coefficients are not unique (you can add

(b / d, - a / d) \cdot t

). Bézout fails when "gcd" is the largest common divisor in a non-PID. In the ring

Z [- 5]

, the elements

a = 2

and

b = 1 + - 5

have only units as common divisors (a "gcd" of

1

in the divisibility sense), yet no elements

x, y

satisfy

2 x + (1 + - 5) y = 1

. The ideal

(2, 1 + - 5)

is not principal. The lesson: Bézout's identity is equivalent to being a principal ideal domain, not a free gift of having gcds. Over

Z

we are safe because

Z

is a PID; the Euclidean Algorithm is precisely what proves this.

Connections

The Euclidean Algorithm is the computational engine behind much of elementary number theory and algebra. Via Bézout's identity it produces modular inverses, the backbone of solving Linear Congruences and the Chinese Remainder Theorem. Bézout's identity also gives the cleanest proof of Euclid's Lemma ( $p ∣ ab \Rightarrow p ∣ a$ or $p ∣ b$ ), which in turn yields the Fundamental Theorem of Arithmetic. Abstractly, a ring on which a Euclidean Algorithm runs is a Euclidean Domain, which is automatically a Principal Ideal Domain and hence a Unique Factorization Domain — a tower of implications all anchored by repeated division. The same algorithm runs verbatim on the polynomial ring $K [x]$ over a field, computing polynomial gcds and underpinning partial fractions and continued fractions.

Real-World Applications

RSA cryptography: computing the private exponent $d \equiv e^{- 1} (mod φ (n))$ uses the Extended Euclidean Algorithm; security relies on coprimality of $e$ and $φ (n)$ .
Modular arithmetic / hashing: finding multiplicative inverses in $Z / n Z$ for error-correcting codes, checksums, and finite-field arithmetic (AES uses gcd over $GF (2^{8})$ ).
Rational number arithmetic: every computer algebra system reduces fractions $a / b$ to lowest terms by dividing out $g cd (a, b)$ .
Continued fractions & Diophantine approximation: the quotients $q_{k}$ of the algorithm are the continued-fraction expansion of $a / b$ , used in calendar design (leap-year rules) and gear-ratio construction (Antikythera mechanism, clockmaking).
Computer graphics & rasterization: Bresenham-style line algorithms and lattice-point counting use gcd to find primitive direction vectors and tiling periods.
Cryptographic key agreement (Diffie–Hellman, elliptic curves): inversion in finite fields via extended gcd is a core primitive.
Signal processing / sampling: the gcd of sampling periods determines the period of a sum of periodic signals.

Historical Development

~300 BCE — Euclid's Elements Books VII & X present the algorithm via repeated subtraction for integers and incommensurable magnitudes.
~500 CE — Aryabhata's kuttaka ("pulverizer") method solves linear Diophantine equations $a x + b y = c$ , equivalent to the extended algorithm, for astronomical calculations.
628 CE — Brahmagupta extends Indian work on linear Diophantine equations and modular reasoning.
1624 — Bachet de Méziriac states the integer solvability of $a x - b y = 1$ when $g cd (a, b) = 1$ in his Problèmes plaisants.
1779 — Étienne Bézout publishes results on resultants and linear combinations; the identity is later named for him (though stated earlier by Bachet).
1801 — Gauss's Disquisitiones Arithmeticae systematizes congruences, gcd, and the structure of $Z / n Z$ .
1844 — Gabriel Lamé proves the worst-case step count is bounded via Fibonacci numbers — an early result in the analysis of algorithms.
Late 1800s–1900s — Dedekind, Kummer, and Noether generalize gcd to ideals, defining Euclidean domains, PIDs, and UFDs.
1976–1978 — Diffie–Hellman and RSA make the extended Euclidean inverse computation a cornerstone of modern cryptography; binary and subquadratic gcd variants (Stein, 1967; Knuth–Schönhage) optimize it for machines.

Subtleties & Limits

The Euclidean Algorithm itself is fully resolved, but its surroundings host genuine difficulties. (1) Which rings are Euclidean? It is unknown for many number rings whether a Euclidean function exists; the question "is the ring of integers of $Q (d)$ norm-Euclidean?" is settled only for finitely many $d$ , and the general "Euclidean but not norm-Euclidean" classification involves deep open conjectures (related to Artin's conjecture on primitive roots). (2) Average-case analysis: the average number of steps for random inputs $\leq N$ is $\sim \frac{12 l n 2}{π ^{2}} ln N$ (Heilbronn, Dixon), but the finest distributional questions connect to dynamical systems and transfer operators (Baladi–Vallée) that remain active research. (3) gcd of polynomials over inexact (floating-point) coefficients is ill-posed — tiny perturbations destroy common factors — motivating ongoing work on "approximate gcd." (4) The relationship between the Euclidean property and being a PID is subtle: every Euclidean domain is a PID, but there exist PIDs (e.g. $Z [\frac{1 + - 19}{2}]$ ) that are not Euclidean for any function — proving non-Euclideanness required new techniques.