Greatest Common Divisor and the Euclidean Algorithm

The greatest common divisor (GCD) of two integers is the largest positive integer dividing both. The Euclidean Algorithm computes it efficiently by repeated division: $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$. It is foundational to number theory and underlies modular arithmetic, fractions, and modern cryptography. The method appears in Euclid's Elements (c. 300 BCE), making it one of the oldest algorithms still in everyday use.

The greatest common divisor of integers $a$ and $b$, written $\gcd (a,b)$, is the largest positive integer that divides both without remainder. It matters because it is the engine behind reducing fractions to lowest terms, solving linear equations over the integers, and inverting elements in modular arithmetic. The surprising fact is that you can find the GCD of enormous numbers — without factoring either one — using only repeated subtraction or division, a process so fast that it is still the standard method after more than two thousand years. The Extended Euclidean Algorithm goes further, expressing $\gcd (a,b)$ as an integer combination $ax+by$, which is the key to division in modular systems like RSA encryption.

The Core Insight

A common divisor of $a$ and $b$ is also a common divisor of $b$ and $a-b$ (and more generally $a-qb$). So replacing the larger number by its remainder upon division by the smaller never changes the set of common divisors — but it shrinks the numbers fast. Repeat until one number becomes $0$; the other is the GCD.

Formal Statement

Divisibility and Common Divisor

For integers $a$ and $d$ with $d\ne 0$, we say $d$ divides $a$ (written $d\mid a$) if there exists an integer $k$ such that $a=dk$.

A common divisor of $a$ and $b$ is an integer $d$ with $d\mid a$ and $d\mid b$. The greatest common divisor $\gcd (a,b)$ is the largest such positive integer (defined for $a,b$ not both zero).

The central recursive identity:

The base case that terminates the recursion:

The Division Algorithm guarantees each step is well-defined:

Bézout's Identity

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

GCD–LCM Relation

For positive integers $a$ and $b$,

Why It Holds / Derivation

The Euclidean Algorithm Terminates and is Correct

If $d\mid a$ and $d\mid b$, then $d\mid (a-qb)=r$, so $d$ divides $b$ and $r$.

Conversely, if $d\mid b$ and $d\mid r$, then $d\mid (qb+r)=a$, so $d$ divides $a$ and $b$.

Imagine tiling a rectangle of size $a\times b$ with the largest possible identical square tiles. Cut off the biggest square you can (side $b$) repeatedly from the $a$-side; what's left is a smaller rectangle $b\times r$. Repeat. The process must end with a rectangle that is perfectly filled by squares of some side $g$ — and that $g$ is $\gcd (a,b)$. Every cut throws away a region that was already tileable by the final square, so the final square size never changes. The algorithm is literally a geometric subtraction game.

Euclidean Algorithm tiling: gcd(48, 18) = 6

Euclid of Alexandria | fl. c. 300 BCE

Euclid, working in Hellenistic Alexandria, compiled the Elements, thirteen books that organized Greek mathematics into a deductive system. Propositions VII.1–VII.2 describe what we now call the Euclidean Algorithm, framed geometrically as anthyphairesis ("reciprocal subtraction") of line segments and quantities. Euclid used it to determine whether two magnitudes are commensurable (have a common measure). His version used repeated subtraction rather than division, but the logic is identical. Almost nothing is known of Euclid's life; his lasting monument is the method of rigorous proof that the Elements established and that this algorithm exemplifies.

Worked Examples

Plain GCD by the Euclidean Algorithm

The last nonzero remainder is $21$. Each line preserves the GCD by Step 1 of the proof.

Extended Euclidean Algorithm — Bézout coefficients

So $x=-9$, $y=47$. Check: $240(-9)+46(47)=-2160+2162=2$. ✓

Common Misconceptions

The GCD threads through much of elementary number theory. Two integers with $\gcd (a,b)=1$ are called coprime, the central condition in Modular Arithmetic for an element to have a multiplicative inverse. Bézout's identity is the engine behind solving Linear Diophantine Equations $ax+by=c$, which are solvable exactly when $\gcd (a,b)\mid c$. The GCD also underlies Fractions in Lowest Terms (divide numerator and denominator by their GCD) and connects to the Fundamental Theorem of Arithmetic via the prime-exponent formula for $\gcd$ and $\mathrm{lcm}$.

Real-World Applications

1. RSA cryptography — generating the private key requires computing a modular inverse, done by the Extended Euclidean Algorithm; $\gcd (e,\varphi (n))=1$ guarantees the inverse exists.
2. Reducing fractions — every computer algebra system and calculator simplifies $\frac{a}{b}$ by dividing both by $\gcd (a,b)$.
3. Gear ratios and mechanical timing — two meshing gears with tooth counts $a$ and $b$ return to their starting alignment after $\mathrm{lcm}(a,b)$ rotations, computed via $[5]$.
4. Audio and signal sampling — converting between sample rates (e.g., 44.1 kHz and 48 kHz) uses the GCD to find the smallest common resampling grid.
5. Tiling and resolution scaling — rendering or cutting a rectangle into identical square units uses $\gcd$ of side lengths, and aspect-ratio reduction (e.g., 1920:1080 → 16:9) divides by their GCD.
6. The Stern–Brocot / continued-fraction methods in computer graphics for best rational approximations rely on Euclidean steps.
7. Error-correcting codes and hashing — polynomial versions of the algorithm over finite fields decode Reed–Solomon codes used in CDs, QR codes, and data storage.

Historical Development

• c. 300 BCE — Euclid, Elements VII.1–2, states the subtraction-based algorithm to test commensurability of magnitudes.
• c. 200 BCE – 100 CE — Chinese mathematicians develop related remainder methods; the Sunzi Suanjing poses problems leading to the Chinese Remainder Theorem.
• 6th century CE — Indian mathematician Aryabhata describes the kuṭṭaka ("pulverizer") method, an extended Euclidean procedure for solving linear congruences.
• 1624 — Bachet de Méziriac states integer solutions of $ax+by=c$ in his recreational mathematics text, foreshadowing Bézout.
• 1779 — Étienne Bézout proves the identity now bearing his name in a more general (polynomial) setting.
• 1801 — Gauss's Disquisitiones Arithmeticae systematizes congruences and the role of $\gcd$ in number theory.
• 1844 — Gabriel Lamé proves that the number of division steps is bounded by a constant times the number of digits — the first explicit algorithm complexity result, linked to Fibonacci numbers.
• 1961 — Josef Stein publishes the binary GCD algorithm, replacing division with shifts and subtractions for efficiency on computers.
• 20th–21st c. — The algorithm becomes foundational in computational number theory, underpinning public-key cryptography (RSA, 1977).

Subtleties & Limits

The Euclidean Algorithm is fast, but precise questions about it remain rich. Its worst case occurs for consecutive Fibonacci numbers, $\gcd (F_{n+1},F_n)$, which forces the maximum number of steps — this links the algorithm to the golden ratio $\phi$, since the step count grows like ${\log }_{\phi }(\min (a,b))$. The average-case behavior connects to deep results in the metric theory of continued fractions (the Gauss–Kuzmin distribution), where the average number of steps involves constants like $\frac{12\ln 2}{{\pi }^2}\ln N$. Generalizing GCD to rings beyond $\mathbb{Z}$ leads to the theory of Euclidean domains and the open subtlety that some unique-factorization domains admit no Euclidean function at all — so "having a GCD" is strictly weaker than "having a Euclidean algorithm."

See Also