Divisibility, GCD, and the Euclidean Algorithm

⚡ Key Takeaways

One-line statement: For integers $a, b$ (not both zero), the greatest common divisor $\gcd(a,b)$ is the largest positive integer dividing both, and the Euclidean Algorithm computes it via repeated division with remainder. Key result in words: $\gcd(a,b)$ can be expressed as an integer linear combination $ax + by$ (Bézout's identity), and the Euclidean Algorithm finds it in $O(\log \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.

💡 The Core Insight

If $d$ divides both $a$ and $b$ , then $d$ divides every integer combination $ax + by$ . In particular $d$ divides $a - qb$ for any integer $q$ . Therefore the set of common divisors of $(a,b)$ equals the set of common divisors of $(b, a - qb)$ . Choosing $q = \lfloor a/b \rfloor$ replaces $a$ with the remainder $r = a \bmod 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.

DefinitionDivisibility

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 \mid a$ , if there exists an integer $q$ with:

1

\quad a = d\,q, \qquad q \in \mathbb{Z}.

Derivation hint: this is a definition; $q$ is the quotient. Note $d \mid 0$ for every nonzero $d$ , since $0 = d \cdot 0$ . Basic properties (for nonzero divisors where needed): $d \mid a$ and $d \mid b$ imply $d \mid (a \pm b)$ ; $d \mid a$ implies $d \mid ka$ for all $k$ ; divisibility is transitive ( $d \mid a$ , $a \mid b \Rightarrow d \mid b$ ); and $d \mid a$ with $a \neq 0$ forces $|d| \le |a|$ .

TheoremDivision Algorithm

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

2

\quad a = b\,q + r, \qquad 0 \le r < b.

Derivation hint: existence by taking $q = \lfloor a/b \rfloor$ so that $r = a - bq \in [0,b)$ ; uniqueness by assuming two representations and bounding their difference below $b$ .

DefinitionGreatest Common Divisor

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

3

\quad d \mid a, \quad d \mid b, \quad \text{and} \quad \bigl(c \mid a \text{ and } c \mid b \implies c \mid d\bigr).

Derivation hint: 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 $\gcd(a,0) = |a|$ for $a \neq 0$ , and $\gcd(0,0)$ is undefined (or set to $0$ ). Integers $a,b$ are coprime (relatively prime) when $\gcd(a,b) = 1$ .

TheoremBézout's Identity

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

4

\quad \gcd(a,b) = a\,x + b\,y.

Derivation hint: let $d$ be the smallest positive value of $\{ax+by : x,y \in \mathbb{Z}\}$ ; show $d \mid a$ and $d \mid b$ via the division algorithm (a smaller positive remainder would contradict minimality), and that any common divisor divides $d$ . Equivalently, $\gcd(a,b)$ is the smallest positive element of the set $\{ax + by\}$ , and that set is exactly the set of all multiples of $\gcd(a,b)$ — i.e. the ideal $(a,b) = (\gcd(a,b))$ in $\mathbb{Z}$ .

TheoremKey Reduction Lemma

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

5

\quad \gcd(a,b) = \gcd(b,r) = \gcd(b,\, a \bmod b).

Derivation hint: show the common-divisor sets of $(a,b)$ and $(b,r)$ coincide. If $c \mid a$ and $c \mid b$ then $c \mid (a - bq) = r$ ; conversely if $c \mid b$ and $c \mid r$ then $c \mid (bq + r) = a$ .

ProofCorrectness and Termination of the Euclidean Algorithm

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

Step 1 — Setup. Define $r_0 = a$ , $r_1 = b$ . Repeatedly apply the division algorithm:

6

\quad r_{k-1} = r_k\, q_k + r_{k+1}, \qquad 0 \le r_{k+1} < r_k.

Derivation hint: 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 > \cdots \ge 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:

7

\quad \gcd(r_{k-1}, r_k) = \gcd(r_k, r_{k+1}).

Derivation hint: direct application of the Key Reduction Lemma to line [6].

Step 4 — Chaining. Composing [7] from $k=1$ up through $k=n$ :

8

\quad \gcd(a,b) = \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_n, r_{n+1}) = \gcd(r_n, 0) = r_n.

Derivation hint: telescope the chain of equalities; the final term uses $\gcd(d,0)=d$ . Hence the algorithm returns $r_n = \gcd(a,b)$ . $\blacksquare$

Complexity. Each two consecutive remainders satisfy $r_{k+2} < r_k / 2$ (since either $r_{k+1} \le 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(\log_2 \min(a,b))$ . The worst case occurs for consecutive Fibonacci numbers (Lamé's theorem), giving roughly $\log_\varphi$ steps where $\varphi$ is the golden ratio.

∎

Figure

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

mathematician · 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 $\sqrt{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.

🧠 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 $\gcd(a,b)$ . Bézout's identity then says: among all combinations $ax+by$ 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.

ExamplePlain Euclidean Algorithm: gcd(1071, 462)

Given: $a = 1071$ , $b = 462$ .

Steps (each line is $r_{k-1} = r_k q_k + r_{k+1}$ ):

9

\quad \begin{aligned} 1071 &= 462 \cdot 2 + 147 \\ 462 &= 147 \cdot 3 + 21 \\ 147 &= 21 \cdot 7 + 0 \end{aligned}

Derivation hint: apply [2] each line; last nonzero remainder is the gcd. The last nonzero remainder is $21$ .

\boxed{\gcd(1071, 462) = 21}

Check: $1071 = 21 \cdot 51$ and $462 = 21 \cdot 22$ , and $\gcd(51,22)=1$ . ✓

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

Given: find $x,y$ with $240x + 46y = \gcd(240,46)$ , then compute $46^{-1} \bmod 240$ if it exists.

Forward pass:

10

\quad \begin{aligned} 240 &= 46 \cdot 5 + 10 \\ 46 &= 10 \cdot 4 + 6 \\ 10 &= 6 \cdot 1 + 4 \\ 6 &= 4 \cdot 1 + 2 \\ 4 &= 2 \cdot 2 + 0 \end{aligned}

Derivation hint: standard division chain; gcd is the last nonzero remainder, $2$ . So $\gcd(240,46) = 2$ .

Back-substitution (express $2$ as a combination):

11

\quad \begin{aligned} 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. \end{aligned}

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

\boxed{240\cdot(-9) + 46\cdot 47 = 2 = \gcd(240,46)}

Modular inverse? Since $\gcd(46,240) = 2 \neq 1$ , $46$ has no inverse mod 240 — the congruence $46t \equiv 1 \pmod{240}$ is unsolvable. (An inverse exists iff the numbers are coprime.) However, $46 \cdot 47 \equiv 2 \pmod{240}$ , so $47$ is a "half-inverse." For contrast: $\gcd(47,240)=1$ , and the same method gives $47^{-1} \equiv 23 \pmod{240}$ since $47\cdot 23 = 1081 = 4\cdot 240 + 1$ .

⚠️ Common mistake

"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 $\mathbb{Z}$ , but in general rings (e.g. polynomial rings) "largest" has no meaning while the divisibility characterization still works. Also beware: $\gcd(a,b) \mid (ax+by)$ for all $x,y$ , but $ax+by$ equals the gcd only for special $x,y$ — Bézout coefficients are not unique (you can add $(b/d, -a/d) \cdot t$ ).

Counterexample

Bézout fails when "gcd" is the largest common divisor in a non-PID. In the ring $\mathbb{Z}[\sqrt{-5}]$ , the elements $a = 2$ and $b = 1 + \sqrt{-5}$ have only units as common divisors (a "gcd" of $1$ in the divisibility sense), yet no elements $x,y$ satisfy $2x + (1+\sqrt{-5})y = 1$ . The ideal $(2, 1+\sqrt{-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 $\mathbb{Z}$ we are safe because $\mathbb{Z}$ is a PID; the Euclidean Algorithm is precisely what proves this.

connection

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 \mid ab \Rightarrow p\mid a$ or $p \mid 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.

🔬 Where this appears

⏳ History

- ~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

ax+by=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

ax - by = 1

when

\gcd(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

\mathbb{Z}/n\mathbb{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.

open-problem

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 $\mathbb{Q}(\sqrt{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 $\le N$ is $\sim \frac{12 \ln 2}{\pi^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. $\mathbb{Z}[\frac{1+\sqrt{-19}}{2}]$ ) that are not Euclidean for any function — proving non-Euclideanness required new techniques.

Divisibility, GCD, and the Euclidean Algorithm

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also