Ch1.3.7 — Of the Greatest Common Divisor of Two Given Numbers
Summary: Presents the Euclidean algorithm for finding the GCD of two integers, works through several examples, and gives a full proof of correctness based on the invariance of the GCD under subtraction.
Sources: chapter-1.3.7
Last updated: 2026-05-01
Why the GCD matters (§451)
To reduce a geometrical ratio to its simplest form, both terms must be divided by their greatest common divisor (GCD). When two numbers share no common divisor other than 1 (they are coprime), the ratio cannot be simplified further. Example: has GCD and is already in lowest terms.
The Euclidean Algorithm (§452)
Rule: To find with :
- Divide by ; call the remainder .
- Divide by ; call the new remainder .
- Continue: divide each divisor by the previous remainder.
- Stop when a division leaves remainder . That last non-zero divisor is .
Example — :
So .
Further examples (§453–454, §460)
| Pair | GCD | Reduced ratio |
|---|---|---|
| already simplest | ||
Proof of correctness (§455–459)
Key lemma: if and , then for any integer (since is a linear combination). The converse also holds: if and , then .
Consequence: the GCD of and equals the GCD of and .
Each division step replaces the pair with , preserving the GCD. The remainder is strictly smaller than , so the sequence of remainders strictly decreases and must eventually reach .
When the remainder is , the last divisor divides its dividend exactly (of the form ). The pair has GCD , which is therefore also the GCD of the original numbers and .