The Euclidean Algorithm as Rectangle-Tiling — Watch the GCD Emerge as the Final Square

The Euclidean algorithm computes the greatest common divisor of two positive integers by repeatedly replacing the larger number with its remainder when divided by the smaller. As symbolic arithmetic, the algorithm is fast but opaque — you push numbers around and a GCD pops out. As geometry, the algorithm is vivid: you take an a \times b rectangle, tile it with squares of the largest possible size, then tile the leftover strip with smaller squares, and keep going until no strip is left. The side length of the final square is exactly \gcd(a, b).

This visualisation transforms the Euclidean algorithm from number-shuffling into something you can see. Once you see it, the algorithm stops looking like magic and starts looking like the most natural thing in the world.

The tiling, step by step

Take the rectangle a \times b with a \geq b.

Cut off the largest b \times b square. What remains is an (a - b) \times b rectangle.
If you can cut off another b \times b square, do so. Keep cutting b \times b squares until the remaining strip is narrower than b.
Now the strip has dimensions r \times b, where r = a \bmod b — the remainder when a is divided by b.
Recurse. Take the new rectangle (of dimensions b \times r, with b \geq r) and repeat the process: cut r \times r squares until a smaller strip remains, then recurse.
Stop when the remaining strip is a perfect square — you have reached \gcd(a, b) \times \gcd(a, b).

Each round of the algorithm corresponds to one Euclidean division step: a = q b + r is "cut q squares of side b, and a strip of width r remains."

Interactive tiling

a = 252: b = 105: phase = all:

Drag $a$ and $b$ to choose any two integers from $2$ to $400$. The tiling proceeds in real time: each square's side equals the current shorter dimension. The phase slider advances through the rounds. The final square's side is $\gcd(a,b)$. Default: $a=252, b=105, \gcd=21$.

Why the final square's side equals the GCD

The geometric claim and the arithmetic claim are the same, translated into different languages.

Arithmetic side. The Euclidean algorithm computes \gcd(a, b) by the repeated identity \gcd(a, b) = \gcd(b, a \bmod b). You keep reducing the pair until one of the two numbers is zero; the other is the GCD.

Geometric side. Each rectangle is tiled with squares of the smaller side's length, leaving a strip whose width is a \bmod b. The tiling recurses: the new rectangle has dimensions b \times (a \bmod b). You keep going until the strip is a perfect square (no remainder left), and the side of that final square is the common divisor.

The bridge. Any square tile that fits inside the rectangle must have a side that divides both a and b — otherwise it could not fit flush against both dimensions simultaneously. Conversely, any common divisor d of a and b defines a tile of side d that fits. So the largest square that can appear as the final tile has side equal to the greatest common divisor.

Why the tiling process terminates: each division round strictly decreases the shorter side of the rectangle (the strip width is always less than the shorter side of the previous rectangle). Since the sides are positive integers, this decreasing sequence of positive integers must eventually hit a perfect square — a rectangle where one side divides the other evenly and the strip is empty. The termination matches the termination of the Euclidean algorithm in arithmetic form.

A second example: \gcd(48, 18)

Start: 48 \times 18 rectangle.
Round 1: cut two 18 \times 18 squares. 48 = 2 \cdot 18 + 12. Strip remaining: 12 \times 18.
Round 2 (flip to 18 \times 12): cut one 12 \times 12 square. 18 = 1 \cdot 12 + 6. Strip remaining: 12 \times 6.
Round 3 (flip to 12 \times 6): cut two 6 \times 6 squares. 12 = 2 \cdot 6 + 0. No strip remaining.

The final square has side 6, so \gcd(48, 18) = 6.

Verify arithmetically: 48 = 2^4 \cdot 3, 18 = 2 \cdot 3^2. The shared prime factorisation is 2 \cdot 3 = 6. \checkmark

What the geometry teaches that the arithmetic hides

Insight 1: the GCD is a shared length scale.

When you tile the rectangle, every square has side length that divides both a and b. The GCD is the largest such length scale — the coarsest grid on which both a and b are integer lengths. Students often think of the GCD as "the largest number dividing both." The geometric view reframes it as "the largest common unit of measurement."

Insight 2: the algorithm's step-count matches the continued fraction.

The sequence of "how many squares fit" in each round — in the 252 \times 105 example, the sequence was 2, 2, 2 — is the continued fraction expansion of \frac{a}{b}: \frac{252}{105} = 2 + \cfrac{1}{2 + \cfrac{1}{2}}. Each round of tiling produces one term of the continued fraction. The Euclidean algorithm and continued fractions are two views of the same object.

Insight 3: Fibonacci pairs are the worst case.

If you want the Euclidean algorithm to take many steps, use consecutive Fibonacci numbers — they cut off exactly one square per round (because each Fibonacci number is just barely bigger than the previous). This geometric intuition is why the worst-case running time of the Euclidean algorithm involves the golden ratio.

Connecting to the Chakravala method

Aryabhata, Brahmagupta, and Bhaskara studied the Euclidean algorithm under the name kuttaka ("the pulveriser") and extended it to solve equations of the form ax + by = c (linear Diophantine equations). They used the algorithm exactly as modern mathematicians do, but applied it to problems far richer than plain GCD computation. The geometric tiling view that we have just seen was already implicit in their treatment — they thought of divisibility problems in terms of commensurable lengths, which is the geometric content of the GCD.

The one-line takeaway

An a \times b rectangle can be tiled with squares of successively smaller sizes, and the side length of the final square equals \gcd(a, b). Each round of tiling is exactly one division step in the Euclidean algorithm. Seeing the algorithm as geometric tiling turns number-shuffling into shape-fitting.