Greatest Common Divisor and the Euclidean Algorithm

⚡ Key Takeaways

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 \bmod 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 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.

DefinitionDivisibility and Common Divisor

For integers $a$ and $d$ with $d \neq 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).

TheoremBézout's Identity

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

4

\quad ax + by = \gcd(a, b).

Moreover, $\gcd(a,b)$ is the smallest positive integer expressible in the form $ax + by$ .

TheoremGCD–LCM Relation

For positive integers $a$ and $b$ ,

5

\quad \gcd(a,b)\cdot \operatorname{lcm}(a,b) = a\,b.

ProofThe Euclidean Algorithm Terminates and is Correct

Step 1 — The key lemma. Suppose $a = qb + r$ . We claim the common divisors of $(a,b)$ are exactly the common divisors of $(b,r)$ . 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$ .

Step 2 — Equal sets, equal maxima. Since the two pairs share the same set of common divisors, they share the same greatest common divisor:

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

Step 3 — Termination. By equation $[3]$ , each remainder satisfies $0 \le r < |b|$ . So the second argument strictly decreases at every step while staying non-negative. A strictly decreasing sequence of non-negative integers must reach $0$ in finitely many steps.

Step 4 — Reading off the answer. When the remainder hits $0$ , equation $[2]$ gives the GCD as the last nonzero remainder. $\blacksquare$

∎

🧠 Intuition

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.

Figure

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

mathematician · 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.

ExamplePlain GCD by the Euclidean Algorithm

Given: Find $\gcd(1071, 462)$ .

Steps — apply $[1]$ repeatedly, recording $a = qb + r$ :

1071 = 2\cdot 462 + 147

462 = 3\cdot 147 + 21

147 = 7\cdot 21 + 0

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

Answer:

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

ExampleExtended Euclidean Algorithm — Bézout coefficients

Given: Find integers $x, y$ with $240x + 46y = \gcd(240, 46)$ .

Forward (find the GCD):

240 = 5\cdot 46 + 10

46 = 4\cdot 10 + 6

10 = 1\cdot 6 + 4

6 = 1\cdot 4 + 2

4 = 2\cdot 2 + 0 \quad\Rightarrow\quad \gcd = 2

Back-substitute to express $2$ as a combination:

2 = 6 - 1\cdot 4

= 6 - 1\cdot(10 - 1\cdot 6) = 2\cdot 6 - 1\cdot 10

= 2\cdot(46 - 4\cdot 10) - 1\cdot 10 = 2\cdot 46 - 9\cdot 10

= 2\cdot 46 - 9\cdot(240 - 5\cdot 46) = 47\cdot 46 - 9\cdot 240

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

Answer:

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

⚠️ Common mistake

The GCD is not found by listing prime factors for large numbers — and you don't need to. Students often think you must factor $a$ and $b$ first. Factoring is computationally hard for large numbers; the Euclidean Algorithm sidesteps it entirely, using only divisions. Also note: $\gcd(a,b)$ is defined for negatives via $\gcd(a,b) = \gcd(|a|,|b|)$ , and conventionally $\gcd(0,0)$ is undefined (or set to $0$ ), since every integer divides $0$ and there is no largest common divisor.

Counterexample

Bézout coefficients are not unique. A student might claim "there is one pair $(x,y)$ with $ax+by=\gcd$ ." In the example above, $240(-9)+46(47)=2$ , but also $240(-9+23)+46(47-120)=240(14)+46(-73)=3360-3358=2$ . In general, all solutions are

\big(x + k\tfrac{b}{g},\; y - k\tfrac{a}{g}\big), \quad k \in \mathbb{Z},

where $g=\gcd(a,b)$ . There are infinitely many.

connection

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 $\operatorname{lcm}$ .

🔬 Where this appears

⏳ History

- 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).

open-problem

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 $\varphi$ , since the step count grows like $\log_\varphi(\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 $\tfrac{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."

Greatest Common Divisor and the Euclidean Algorithm

Formal Statement

Why It Holds / Derivation

Worked Examples

Common Misconceptions

Real-World Applications

Historical Development

Subtleties & Limits

See Also