Euclidean algorithm — GCD computation: Worked examples

Before anything, one word we lean on constantly: a divisor of a number $n$ is a whole number that divides $n$ with zero remainder. " $d ∣ n$ " (read " $d$ divides $n$ ") is shorthand for " $n$ is a whole multiple of $d$ ". The division algorithm promises: for any integer $a$ and any positive $b$ , there is exactly one pair $(q, r)$ with $a = b q + r, 0 \leq r < b .$ Here $q$ is the quotient (how many whole copies of $b$ fit inside $a$ ) and $r$ is the remainder (the leftover, always smaller than $b$ ). Every example below is just this line, applied over and over.

The scenario matrix

Every input pair $(a, b)$ falls into one of these cells. Our examples together hit all of them.

Cell	Situation	What could go wrong	Example
A	Both positive, $a > b$ , standard	nothing — the baseline	Ex 1
B	Both positive, $a < b$	do we need to swap first?	Ex 2
C	One divides the other exactly	remainder $0$ on step one	Ex 3
D	Coprime pair (answer is $1$ )	mistaking $1$ for "failed"	Ex 4
E	A zero input, $g cd (a, 0)$	the degenerate edge	Ex 5
F	Negative input(s)	signs — does $g cd$ even make sense?	Ex 6
G	Word problem (tiling a floor)	translating words into a $g cd$	Ex 7
H	Exam twist ( $g cd$ of three numbers)	chaining the algorithm	Ex 8

The greatest common divisor $g cd (a, b)$ is the largest whole number that divides both $a$ and $b$ . Read the matrix rows top to bottom — each strips away one assumption the baseline quietly made.

Cell A — the baseline

Worked example Example 1 (Cell A):

$g cd (84, 30)$ Forecast: guess the answer before reading. Biggest number dividing both $84$ and $30$ ?

Step 1. Divide the bigger by the smaller: $84 = 30 \cdot 2 + 24$ , so remainder $r = 24$ . Why this step? This is the whole engine. The Euclidean Lemma from the parent note says $g cd (84, 30) = g cd (30, 24)$ — the remainder inherits every common divisor, so we may forget $84$ .

Step 2. $30 = 24 \cdot 1 + 6$ , so $r = 6$ . Now $g cd (30, 24) = g cd (24, 6)$ . Why this step? Same lemma again. Notice the numbers strictly shrink ( $30 \to 24 \to 6$ ); this is why the process must end.

Step 3. $24 = 6 \cdot 4 + 0$ . Remainder is $0$ — stop. The last non-zero remainder, $6$ , is the answer. Why this step? Remainder $0$ means $6 ∣ 24$ exactly, and since $6$ was already a divisor of everything above it, $6$ divides both originals.

Answer: $g cd (84, 30) = 6$ .

Verify: $84 = 6 \cdot 14$ and $30 = 6 \cdot 5$ . Both exact ✓. And $14, 5$ share no common factor, so $6$ really is the greatest. ✓

Look at the figure: each step chops the longer bar into copies of the shorter bar, and the shrinking leftover is what we carry forward.

Figure — Euclidean algorithm — GCD computation

Cell B — smaller number first (do we swap?)

Worked example Example 2 (Cell B):

$g cd (30, 84)$ — the inputs are "backwards" Forecast: should we panic and swap? Guess whether the answer differs from Example 1.

Step 1. Divide $30$ by $84$ . Since $30 < 84$ , it fits zero times: $30 = 84 \cdot 0 + 30$ , so $r = 30$ . Why this step? The division algorithm still applies with $q = 0$ . The remainder is just $30$ itself, because you can't subtract even one whole $84$ .

Step 2. Apply the lemma: $g cd (30, 84) = g cd (84, 30)$ . The pair has silently swapped itself — no manual sorting needed. Why this step? This is exactly the parent note's Mistake 2: the algorithm self-corrects. One "wasted" step and we're back to Example 1.

Steps 3–5. Identical to Example 1: $g cd (84, 30) = 6$ .

Answer: $g cd (30, 84) = 6$ .

Verify: order of arguments never changes a $g cd$ (a common divisor of two numbers doesn't care which you name first). Matches Example 1 ✓.

Cell C — one divides the other

Cell D — coprime pair (answer is 1)

Cell E — a zero input (the degenerate edge)

Worked example Example 5 (Cell E):

$g cd (42, 0)$ Forecast: what on earth is the "greatest divisor of $0$ "? Guess.

Step 0 (definition check). Every integer divides $0$ , because $0 = d \cdot 0$ for any $d$ . So the common divisors of $42$ and $0$ are simply all divisors of $42$ — and the greatest of those is $42$ itself. Why this step? We can't blindly divide by $b = 0$ ; instead we read the base case of the recursion: $g cd (a, 0) = a$ .

Step 1 (the recursion agrees). The parent's rule states $g cd (a, b) = a$ when $b = 0$ . Plug in: $g cd (42, 0) = 42$ . Why this step? This base case is precisely the line every recursion terminates on — that's why it's baked into the definition.

Answer: $g cd (42, 0) = 42$ .

Verify: $42 ∣ 42$ ✓ and $42 ∣ 0$ (since $0 = 42 \cdot 0$ ) ✓. (Note: $g cd (0, 0)$ is conventionally $0$ — no greatest divisor exists, so we take the boundary value.)

Cell F — negative inputs

Worked example Example 6 (Cell F):

$g cd (- 48, 18)$ Forecast: can a divisor be negative? Guess whether the sign changes the answer.

Step 1 (strip the sign). Divisors come in $\pm$ pairs: if $d ∣ n$ then $d ∣ (- n)$ too, since flipping a sign never changes whether the division is exact. So common divisors of $- 48$ and $18$ are the same as those of $48$ and $18$ . We define $g cd$ to be the positive representative. Why this step? "Greatest" is meaningless if negatives are allowed (you could always go more negative). We fix the convention: $g cd$ is $\geq 0$ . Hence $g cd (- 48, 18) = g cd (48, 18)$ .

Step 2. $48 = 18 \cdot 2 + 12 \Rightarrow g cd (48, 18) = g cd (18, 12)$ . Step 3. $18 = 12 \cdot 1 + 6 \Rightarrow g cd (18, 12) = g cd (12, 6)$ . Step 4. $12 = 6 \cdot 2 + 0 \Rightarrow$ stop. Answer $6$ .

Answer: $g cd (- 48, 18) = 6$ .

Verify: $- 48 = 6 \cdot (- 8)$ ✓ (exact) and $18 = 6 \cdot 3$ ✓. The magnitude is all that mattered. If both were negative, e.g. $g cd (- 48, - 18)$ , the same reasoning gives $6$ as well. ✓

Cell G — word problem (tiling)

Worked example Example 7 (Cell G): the square-tile floor

Statement: A hall floor is $1071 cm$ long and $462 cm$ wide. You must cover it with identical square tiles, whole tiles only, no cutting. What is the largest tile side that fits both dimensions exactly?

Forecast: guess whether the tile side is closer to $10$ cm or $100$ cm.

Step 1 (translate). A square of side $s$ tiles the length exactly $⟺ s ∣ 1071$ ; it tiles the width exactly $⟺ s ∣ 462$ . The largest such $s$ is $g cd (1071, 462)$ . Why this step? "Fits both perfectly, as big as possible" is the definition of greatest common divisor — the word problem is a $g cd$ in disguise.

Step 2. $1071 = 462 \cdot 2 + 147 \Rightarrow g cd (1071, 462) = g cd (462, 147)$ . Step 3. $462 = 147 \cdot 3 + 21 \Rightarrow g cd (462, 147) = g cd (147, 21)$ . Step 4. $147 = 21 \cdot 7 + 0 \Rightarrow$ stop. Answer $21$ . Why these steps? Pure Euclidean peeling on the two side lengths.

Answer: the largest tile is $21 cm \times 21 cm$ .

Verify (with units). Length: $1071/21 = 51$ whole tiles ✓. Width: $462/21 = 22$ whole tiles ✓. Total $51 \times 22 = 1122$ tiles, all whole — no cutting. ✓ The tiling picture below shows the shrinking-square idea geometrically.

Cell H — exam twist (three numbers)

Worked example Example 8 (Cell H):

$g cd (84, 30, 66)$ Statement: find the greatest number dividing all three of $84$ , $30$ , $66$ .

Forecast: guess whether it's larger or smaller than $g cd (84, 30) = 6$ from Example 1.

Step 1 (chain the rule). The key fact: $g cd (a, b, c) = g cd (g cd (a, b), c)$ . A number divides all three iff it divides the first two and the third. Why this step? The Euclidean algorithm only eats two inputs at a time. Nesting lets us reuse it — no new machinery needed.

Step 2. Reuse Example 1: $g cd (84, 30) = 6$ .

Step 3. Now $g cd (6, 66)$ : $66 = 6 \cdot 11 + 0$ , so it's $6$ . Why this step? $6 ∣ 66$ exactly, so the inner GCD survives untouched.

Answer: $g cd (84, 30, 66) = 6$ .

Verify: $84 = 6 \cdot 14$ , $30 = 6 \cdot 5$ , $66 = 6 \cdot 11$ — all exact ✓. And $14, 5, 11$ share no common factor, so $6$ is greatest ✓. Order doesn't matter: nesting the other way, $g cd (30, 66) = 6$ then $g cd (6, 84) = 6$ , same result ✓.

Recall

Recall Why does

$g cd (a, 0) = a$ ? Every integer divides $0$ (since $0 = d \cdot 0$ ), so the common divisors of $a$ and $0$ are exactly the divisors of $a$ ; the greatest is $a$ itself. Why does swapping to smaller-first cost only one step? ::: The first division gives quotient $0$ and remainder $= a$ , so $g cd (a, b)$ becomes $g cd (b, a)$ — one wasted round, then normal. Does a negative input change the answer? ::: No — divisors come in $\pm$ pairs, and $g cd$ is fixed as the positive representative, so $g cd (- 48, 18) = g cd (48, 18) = 6$ . How do you $g cd$ three numbers with a two-input algorithm? ::: Nest it: $g cd (a, b, c) = g cd (g cd (a, b), c)$ .

Connections

2.5.7-euclidean-algorithm-gcd-computation — the parent method these cases stress-test
2.5.01-divisibility-and-division-algorithm — the $a = b q + r$ line every example runs on
2.5.03-fundamental-theorem-of-arithmetic — cross-checking $g cd$ via shared prime factors
2.5.08-extended-euclidean-algorithm — next: recover $x, y$ with $a x + b y = g cd$
2.5.10-bezouts-identity — why coprime (Cell D) guarantees a solvable $a x + b y = 1$
2.5.15-modular-arithmetic-basics — coprimality is what lets modular inverses exist
3.2.04-rsa-encryption — the real-world payoff of the coprime and inverse machinery
1.4.09-fibonacci-sequence — the worst-case inputs that make the algorithm slowest