Vibe Engines Learn
Algorithm · Math

The Biggest Tile That Fits.

Don't memorize the Euclidean algorithm — see it as tiling. The greatest common divisor of two numbers is the side of the largest square that fills their rectangle with no gap. Peel off the biggest square that fits, tile the leftover strip, repeat. The last square that fits exactly is the GCD — and that is precisely the ancient rule gcd(a, b) = gcd(b, a mod b), older than algebra and still unbeaten.

gcd = largest tiling square · (a, b) → (b, a mod b) · stop at 0 · O(log n)
GCD

The largest number dividing both a and b — the biggest square tile that fills their rectangle.

KEY FACT

gcd(a, b) = gcd(b, a mod b) — removing whole squares never changes the answer.

REDUCE

Replace the pair (a, b) with (b, a mod b). The numbers shrink fast.

STOP AT ZERO

When the remainder hits 0, the other number is the GCD. gcd(x, 0) = x.

euclid.sim — gcd(48, 18) by tiling a 48×18 rectangle
Ready

A 48 × 18 rectangle. The GCD is the side of the biggest square that could tile it perfectly. Press Step: peel off the largest square that fits, then tile whatever strip is left over — until nothing remains.

gcd(a, b) = gcd(b, a mod b),   gcd(x, 0) = x
—
Remainder
?
GCD

Why removing squares is safe

Picture the two numbers as the sides of a rectangle, 48 by 18. Any square tile that fills it perfectly must have a side dividing both 48 and 18 — so the largest such tile is exactly the GCD. Now the trick: chop off as many 18 by 18 squares as fit along the long side. Two fit, using up 36, and a 12 by 18 strip is left. Crucially, a tile that fills the original rectangle also fills that strip, and vice versa — cutting off whole squares removes nothing that matters. So the problem shrinks to tiling a 12 by 18 rectangle, then 12 by 6, then 6 by 6, which tiles exactly. The final square has side 6: gcd(48, 18) = 6. In numbers, each peel is one a mod b.

01

The insight

Write a = q·b + r. Any common divisor of a and b also divides r = a − q·b, so gcd(a, b) = gcd(b, r).

02

Reduce

Replace (a, b) with (b, a mod b) — the larger value becomes the remainder.

03

Repeat

Remainders shrink at least by half every two steps, so only about log-many steps are needed.

04

Terminate

When b = 0, the other number is the GCD, because every number divides 0.

Time
O(log n)
Space
O(1)
Worst case
Fibonacci
Idea
gcd(b, a%b)

The algorithm is two lines of code and it never gets stuck: the remainder strictly decreases and is bounded below by zero, so it must terminate — fast. The slowest inputs are consecutive Fibonacci numbers, and even then Lamé's theorem caps the step count at roughly five times the digit count of the smaller number. This same reduction is the engine behind reducing fractions, the extended Euclidean algorithm for modular inverses, and the sieve-adjacent world of number theory. Simple idea, enormous reach.

Check yourself

1 · The Euclidean algorithm reduces gcd(a, b) to…

The modulo form does all the repeated subtractions at once: (a, b) becomes (b, a mod b), and the common divisors are unchanged.

2 · When does the algorithm stop, and what is the answer?

Once the remainder becomes 0, the other number divides it (everything divides 0), so that number is the GCD.

3 · What does the GCD mean geometrically?

A square tiles the rectangle with no gap only if its side divides both dimensions, so the biggest such square has side gcd(a, b).

Questions

Why is it so fast?

Every two iterations the larger number drops by at least half, so the values shrink geometrically — O(log min(a, b)) steps. The worst case is consecutive Fibonacci numbers; Lamé's theorem bounds the steps at about five times the digit count of the smaller input.

Subtraction version vs modulo version?

The original Euclid repeatedly subtracts the smaller number from the larger until they match. The modulo version collapses all those subtractions into one a mod b, which is dramatically faster when the two numbers differ a lot in size. Same GCD, better speed.

What is the extended Euclidean algorithm?

A version that also returns integers x and y with a·x + b·y = gcd(a, b). Those coefficients give modular inverses, which underpin RSA and other cryptography, so the humble GCD reaches surprisingly far.

Peel a square, tile the rest, repeat.

The GCD is the biggest tile that fills the rectangle — and finding it is just gcd(a, b) = gcd(b, a mod b) until nothing is left.

← All algorithms Sieve of Eratosthenes → Big-O Cheatsheet →
Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →