Noesis
1.1.10 · D2Arithmetic & Number Systems

Visual walkthrough — HCF (GCD) — prime factorization method, Euclidean algorithm

1,744 words8 min read↑ Back to topic

Everything below is built with rectangles and tiles. We never assume you know what a "divisor" is — we draw it.

Step 1 — What "divides" even means, as a picture

In the figure: a length of is covered by four sticks of — flush at the end, remainder . Below it, leaves a gap: does not divide .

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm

Step 2 — A common divisor, and the target we're hunting

WHAT the figure shows: two floors, and . A stick of length fits both. A stick of length also fits both — and it's longer. A stick of fits neither. The longest stick fitting both is , so .

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm

Step 3 — The one magic fact: divisors survive subtraction

WHY it's true — look at the figure. If the whole is made of whole sticks, and the part you removed () is also made of whole sticks, then the leftover is whole-sticks-minus-whole-sticks, which is still a whole number of sticks. No stick ever had to be cut.

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm

Step 4 — Subtracting many times at once = the remainder

WHAT the figure does: it lays copies of along , then marks the leftover stub . Since is smaller than , we can't fit another whole — that's why .

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm

Step 5 — Repeat: the problem shrinks toward zero

WHAT the figure shows: a staircase of shrinking rectangles for : Each remainder (pink) becomes the tile for the next row. The pairs march , every arrow preserving the HCF by Step 4.

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm

Step 6 — The floor edge case: why

WHAT the figure shows: a length- floor tiled by one stick of length (perfect), and an empty -floor that any stick "tiles" trivially. The biggest common tile is .

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm

Step 7 — Degenerate & edge inputs (never hit a surprise)

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm

The one-picture summary

Below: the entire derivation compressed. Left, the shrinking staircase of with the pink leftover always feeding the next tile row. Right, the arrows all carry the same HCF (Step 4) down to , where Step 6 reads off . The tile that finally lays flush — — is the answer.

Figure — HCF (GCD) — prime factorization method, Euclidean algorithm
Recall Feynman retelling (plain words)

Imagine two floors, a long one and a short one, and you want the biggest square tile that covers both perfectly. Here's the trick: chop the long floor down by removing as many whole copies of the short floor as fit — the little leftover stub is the remainder. Now here's the magic: any tile that covered both original floors also covers that stub (whole minus whole is still whole tiles). So the biggest common tile hasn't changed — but the numbers got smaller. Now play the same game with the short floor and the stub. Keep going; the stubs keep shrinking and must eventually reach zero. The moment a floor divides evenly (stub ), the tile you were using in that step is the biggest tile that fit everything all along. That's Euclid: divide, take the leftover, repeat, and the last leftover before zero is your answer.

Connections