Euclidean algorithm — GCD computation: Visual walkthrough

Step 0 — The two words we need first

Before any algorithm, two plain ideas.

Look at the picture: the coral strip is $a$ , the mint strip is $b$ , and the little lavender tile $d$ fits into both with no gap.

Figure — Euclidean algorithm — GCD computation

That tile is what we are hunting. We could hunt it by factoring — but factoring huge numbers is slow. So we look for a cheaper move. (See 2.5.03-fundamental-theorem-of-arithmetic for the factoring route.)

Step 1 — Lay the small strip against the big one

WHAT. Put the mint strip (length $b$ ) down repeatedly along the coral strip (length $a$ ) as many whole times as it fits. Call that count $q$ (the quotient). Whatever sticks out past the last full copy is the leftover $r$ (the remainder).

WHY. This is the only thing we are allowed to do with lengths and no calculator: measure one against the other. It turns the vague "big number" into a clean sentence.

PICTURE. Below, $q = 2$ whole mint sticks fit into coral, and the coral tail past them is $r$ .

This " $a = b q + r$ " is the same division algorithm from 2.5.01-divisibility-and-division-algorithm. Notice $r = a - b q$ — the leftover is what remains after subtracting whole sticks.

Step 2 — The magic claim: the leftover keeps the same tiles

WHAT. Claim: every tile that fits both $a$ and $b$ also fits $r$ , and vice-versa. So $a$ and $b$ share exactly the same common divisors as $b$ and $r$ .

WHY. If this is true, the biggest shared tile is identical for both pairs: $g cd (a, b) = g cd (b, r) .$ Then we can throw away the big number $a$ and work with the smaller pair $(b, r)$ — a genuinely easier problem.

PICTURE. Watch the lavender tile. It fills $b$ exactly, so it fills the whole run of $q$ sticks exactly ( $b q$ ). The leftover is $r = a - b q$ — a difference of two things the tile fills — so the tile must fill $r$ too, with no gap.

The proof in plain arithmetic: if $d$ fits $b$ then $d$ fits $b q$ (a whole number of $b$ 's). Fitting $a$ and fitting $b q$ means $d$ fits their difference $a - b q = r$ . Nothing magic — just "a divisor of two numbers divides their difference."

Step 3 — Rename and repeat (the recursion)

WHAT. Since $(b, r)$ has the same GCD as $(a, b)$ , forget $a$ . Rename: the old stick $b$ becomes the new long strip, the old leftover $r$ becomes the new stick. Then measure again.

WHY. Each pass makes the numbers smaller but keeps the answer identical. That's the whole trick: shrink the problem without changing its solution.

PICTURE. The old leftover (coral tail) is picked up and stood on end as the new measuring stick against the old mint stick.

Step 4 — Why it must stop (termination)

WHAT. The remainders form a strictly shrinking chain of non-negative whole numbers: $b > r_{1} > r_{2} > r_{3} > \dots \geq 0.$

WHY. Every remainder is smaller than the stick that made it (Step 1 guaranteed $r < b$ ). A decreasing sequence of whole numbers cannot fall forever — it must hit $0$ . When some remainder is $0$ , the stick fit exactly, and that stick is the GCD (Mistake 3 in the parent: remainder $0$ means "perfect fit," not "no answer").

PICTURE. A staircase of strips, each shorter than the last, ending at a strip that tiles the one before it perfectly (leftover $= 0$ ).

Step 5 — Worked case: $g cd (48, 18)$ as falling strips

WHAT. Run the picture on real numbers.

Long $a$	Stick $b$	$a = b q + r$	Leftover $r$
48	18	$48 = 18 \cdot 2 + 12$	12
18	12	$18 = 12 \cdot 1 + 6$	6
12	6	$12 = 6 \cdot 2 + 0$	0

WHY. Each row is Step 1 done once; each down-arrow is Step 3's rename. The leftover reaches $0$ at row 3, so the last non-zero stick, $6$ , is the answer.

PICTURE. Three shrinking bars: $48 \to 18 \to 12 \to 6$ , with $6$ tiling $12$ exactly.

$g cd (48, 18) = 6.$

Step 6 — Edge cases you must never trip on

WHAT & WHY. Four corners the picture must survive.

PICTURE. Four mini-panels: the swap, the instant fit, the empty stick, and the long coprime staircase ending at a unit tile.

The one-picture summary

Everything on one canvas: the division $a = b q + r$ that makes a leftover, the arrow showing the leftover inherits every tile, the rename that shrinks the pair, and the staircase falling to a perfect fit whose stick is the GCD.

Recall Feynman retelling — say it like you'd tell a friend

You've got two sticks. Lay the short one along the long one as many times as it goes; there's a little scrap left over that's shorter than the short stick. Here's the secret: any ruler that measures both original sticks perfectly also measures that scrap perfectly — because the scrap is just the long stick minus a whole number of short sticks. So I don't lose any answer by throwing the long stick away and keeping (short stick, scrap). Do it again. The scraps get smaller every single time and are never negative, so eventually a scrap fits perfectly with nothing left over. That last perfectly-fitting stick is the biggest ruler that measures both — the GCD. If I hand it two numbers backwards, the first step just flips them. If one number is $0$ , there's nothing to measure and the other number is the answer. That's the entire algorithm, and it's why it's so fast: the numbers shrink toward zero instead of us hunting for prime factors.

Recall Quick self-test

Why can we replace $(a, b)$ with $(b, a mod b)$ ? ::: Because $r = a - b q$ , so any divisor of $a$ and $b$ divides $r$ (and vice-versa) — both pairs share the same common divisors, hence the same greatest one. What guarantees the algorithm stops? ::: Remainders strictly decrease ( $r < b$ ) and stay $\geq 0$ ; a shrinking chain of whole numbers must reach $0$ . What is the GCD once the loop ends? ::: The last non-zero remainder — the stick that finally divided evenly. What is $g cd (a, 0)$ ? ::: $a$ , the base case.

Connections

2.5.01-divisibility-and-division-algorithm — $a = b q + r$ is the engine of every step here.
2.5.03-fundamental-theorem-of-arithmetic — the slower factoring route we deliberately avoid.
2.5.08-extended-euclidean-algorithm — run these steps backward to get $x, y$ .
2.5.10-bezouts-identity — that $a x + b y = g cd (a, b)$ falls out of the same picture.
2.5.15-modular-arithmetic-basics — $a mod b$ is exactly the leftover we used.
3.2.04-rsa-encryption — why "fast GCD without factoring" matters in practice.
1.4.09-fibonacci-sequence — the slowest inputs are Fibonacci neighbours.