The Euclidean Algorithm, Seen as Squares

After reading this you can find the greatest common divisor of two numbers by tiling a rectangle with squares, and you can connect each square to a line of the usual remainder recursion.

What the algorithm does, and one picture to hold onto

The greatest common divisor of two whole numbers, written \gcd(a, b), is the largest number that divides both without remainder. For 48 and 36 the answer is 12, because 12 divides 48 four times and 36 three times, and nothing larger does.

Euclid found this without factoring either number. His method has a shape you can see. Draw a rectangle 48 wide and 36 tall. Lay down the largest square that fits: a 36 by 36 square. That leaves a 12 by 36 strip. Fill that strip with 12 by 12 squares. Exactly three of them fit, with nothing left over. The side of that last square, 12, is the answer.

The visualizer draws this for you. Each round of squares gets its own colour, and the leftover strip becomes the next rectangle. When a square tiles a rectangle perfectly, the algorithm stops, and that square's side is the gcd.

When squares help and when to just divide

The geometric picture is a teaching device, not the fast route. If you only want the number, dividing is quicker. The value of the tiling is that it makes three facts obvious: the gcd of two numbers equals the gcd of the smaller number and the leftover, the leftover is always smaller, and the process must end because the numbers keep shrinking toward a positive divisor.

Reach for the visual form when you are learning why the algorithm works, teaching it, or checking a hand computation. Reach for plain division inside a program, where you write a % b in a loop and never draw anything. For very large numbers the tiling becomes unwieldy: a 100000 by 3 rectangle needs a row of tiny squares that no screen shows well, while the arithmetic finishes in two steps.

The gcd is defined for any two integers not both zero. This article uses positive whole numbers because that is what you can tile. For negative inputs, take absolute values first: \gcd(-48, 36) = 12.

The formula and why subtraction becomes remainder

The recursion at the heart of everything is short.

\gcd(a, b) = \gcd(b, a \bmod b)

Here a \bmod b is the remainder when a is divided by b. The base case is \gcd(a, 0) = a: when the remainder hits zero, the last divisor is the answer.

Why is this true? Any number that divides both a and b also divides a - b, and by extension divides a - qb for any whole number q. Choose q as large as possible without going negative, and what remains is exactly a \bmod b. So the common divisors of (a, b) are the same set as the common divisors of (b, a \bmod b). Same set means same maximum, which is the gcd.

The link to squares is direct. Peeling off one square of side b from an a \times b rectangle is one subtraction, a - b. Peeling off as many b-squares as fit in a row is one division: you fit q = \lfloor a / b \rfloor squares and the strip that remains has width a \bmod b. One coloured band in the picture equals one line of the recursion.

A worked example with the demo numbers

Tiling 48 by 36

Start with the defaults, a = 48 and b = 36. Follow the remainder each step.

\gcd(48, 36): fit \lfloor 48/36 \rfloor = 1 square of side 36. Remainder 48 - 36 = 12. Now solve \gcd(36, 12).
\gcd(36, 12): fit \lfloor 36/12 \rfloor = 3 squares of side 12. Remainder 36 - 36 = 0. Now solve \gcd(12, 0).
\gcd(12, 0) = 12. The remainder is zero, so the last divisor, 12, is the gcd.

The picture shows one large square (side 36) in the first colour, then three squares (side 12) in the second colour that fill the leftover strip exactly. Total: 4 squares, 2 rounds of colour.

Each row is one division step of gcd(48, 36).
Step	a	b	Quotient q	Remainder a mod b	Squares of side b
1	48	36	1	12	1
2	36	12	3	0	3
3	12	0	stop	gcd = 12	0

Reading the picture and the step list together

Three quantities in the visual carry meaning. The number of coloured bands equals the number of division steps. The count of squares in a band equals the quotient q for that step. The side of the final square equals the gcd.

You can also read the whole rectangle as a fraction. The ratio a/b = 48/36 reduces to 4/3 because you divide both by the gcd 12. The quotients 1, 3 are the continued-fraction expansion of that ratio: 48/36 = 1 + 1/3. Every gcd computation is secretly building a continued fraction, and each coloured band is one term of it.

When the gcd is 1 the two numbers are coprime: no square smaller than 1 by 1 will ever tile perfectly, and the last band is always unit squares. When one number divides the other cleanly, the algorithm finishes in a single band. For 36 and 12 you fit exactly 3 squares and stop, so the gcd is 12 in one step.

The worst case: consecutive Fibonacci numbers

The slowest inputs for their size are consecutive Fibonacci numbers. Take 55 and 34. Every division gives quotient 1, so only one square peels off each round, and the remainders march down the Fibonacci sequence: 34, 21, 13, 8, 5, 3, 2, 1, 0.

Each bar is the larger value at one step. Because every quotient is 1, the sequence is just the Fibonacci numbers counting down, and it takes 8 steps to reach gcd 1.

This is Lamé's theorem in concrete form: the number of division steps never exceeds about 5 times the number of decimal digits in the smaller input. Fibonacci pairs sit right at that bound. Compare 55 and 34 (8 steps) with 48 and 36 of similar size (2 steps). Big quotients finish fast; a run of quotients equal to 1 is the slow road.

Common mistakes

Do not stop at the first square. A single large square peeling off is one step, not the end. The algorithm ends only when a square divides its rectangle with zero leftover strip. In \gcd(48, 36) the first 36-square leaves a 12-wide strip, so you keep going.

A second mistake is reading the gcd off the biggest square instead of the last one. The first square in \gcd(48, 36) has side 36, but 36 is not the gcd. The gcd is the side of the final square that tiles perfectly, which is 12.

A third is confusing quotient with remainder. Fitting 3 squares of side 12 means the quotient is 3; the remainder is the leftover width, which is 0 here. The visualizer lists both so you never have to guess.

Finally, order does not matter for the answer but does for the first step. \gcd(36, 48) gives the same 12, but step one fits zero squares of side 48 and simply swaps the two numbers, wasting a step. The tiling handles this by always peeling the smaller side, so a tall-narrow and a short-wide rectangle behave the same after one swap.

Related tools on this site

Continued fractions and mediants show up again in Ford Circles & Farey Fractions, where the same 1s and 3s that count your squares build the Stern-Brocot tree. The golden ratio behind the Fibonacci worst case reappears as the packing angle in Phyllotaxis. For another number-theory pattern you can watch emerge, cross out multiples in the Sieve of Eratosthenes or count prime splittings in the Modular Times Table. If recursion drawn as structure appeals to you, the Tower of Hanoi unfolds its own step count of 2^n - 1.

Frequently asked questions

Why is the last square's side the gcd and not the first?

Each square you peel off leaves a strip whose common divisors match the original rectangle's. The gcd is preserved at every step. Only the final square divides its rectangle with no leftover, which means its side divides everything above it, so it is the largest shared divisor.

What if the two sides are equal?

Then one square of that side fills the whole rectangle in a single step, and the gcd equals the side. For \gcd(20, 20) you place one 20 by 20 square, remainder 0, gcd 20.

How many steps does it take in the worst case?

By Lamé's theorem, no more than about 5 times the digit count of the smaller number. Consecutive Fibonacci numbers hit that bound: \gcd(55, 34) needs 8 steps.

Does the algorithm work for fractions or decimals?

Only integers tile with whole squares. To reduce a fraction like 48/36, divide both parts by \gcd(48, 36) = 12 to get 4/3. The quotients you collect, 1 then 3, are exactly the continued-fraction form of that ratio.

What does gcd equal to 1 mean geometrically?

The two numbers are coprime, so no square larger than 1 by 1 ever tiles perfectly. The final coloured band is always made of unit squares. That is why coprime pairs tend to need more steps.

Try it yourself in the tool