On this page
Take a sheet 252 cm by 105 cm and cut it into squares, always the largest square that fits. The side of the last, smallest square is the highest common factor (HCF) of 252 and 105. That cutting process is Euclid's algorithm, drawn instead of written.
Euclid's Elements, Book VII, Proposition 2 sets the task "To find the greatest common measure of two given numbers not relatively prime" and solves it by repeatedly subtracting the smaller number from the larger (Clark University edition of the Elements). The Elements dates from about 300 BC (Euclidean algorithm, Wikipedia). Cutting one square at a time is that subtraction; division just groups the cuts.
How does a rectangle show Euclid's division algorithm?
Work through the 252 by 105 rectangle one batch at a time.
Lay squares of side 105 along the long edge. Two fit (210 cm) and a strip 42 cm wide is left. In symbols: 252 = 2 × 105 + 42.
The leftover strip is 105 by 42. Squares of side 42 now fit twice, leaving a strip 21 wide: 105 = 2 × 42 + 21.
The new leftover is 42 by 21. Two squares of side 21 fill it exactly: 42 = 2 × 21 + 0.
Each line of the division algorithm is one batch of equal squares. The quotient tells you how many squares in the batch; the remainder is the width of the strip left over. The last non-zero remainder, 21, is the HCF. Check with prime factors: 252 = 2² × 3² × 7 and 105 = 3 × 5 × 7, so the common part is 3 × 7 = 21.
Why is the last square's side the HCF?
There are two things to show: 21 divides both sides, and nothing larger does.
21 is a common factor. The 21 squares fill the 42 strip exactly, so 42 is a whole number of 21s. Then 105 = 2 × 42 + 21 is too, and so is 252 = 2 × 105 + 42. Every square in the picture can be cut into 21 by 21 tiles, so the whole rectangle can.
Nothing larger works. Any number d that divides 252 and 105 also divides 252 − 2 × 105 = 42, and then 105 − 2 × 42 = 21. So every common factor divides 21, and none can be bigger than 21.
The same argument works at every step, so HCF(a, b) = HCF(b, r), where r is the remainder. The picture keeps that fact in view.
How many steps will Euclid's algorithm take?
Two counts come straight from the division lines. The number of steps is the number of division lines, and the number of squares is the sum of the quotients. For 252 by 105 the quotients are 2, 2 and 2: three steps, six squares.
For an upper limit, Gabriel Lamé proved in 1844 that the algorithm never needs more steps than five times the number of decimal digits in the smaller number (Euclidean algorithm, Wikipedia). 105 has three digits, so at most 15 steps; we needed three.
The slowest pairs are consecutive Fibonacci numbers: the smallest pair needing exactly n steps is the Fibonacci pair F(n+2) and F(n+1) (Lamé's theorem, Wolfram MathWorld). Try 13 by 8:
13 = 1 × 8 + 5
8 = 1 × 5 + 3
5 = 1 × 3 + 2
3 = 1 × 2 + 1
2 = 2 × 1 + 0
Five steps, six squares, HCF 1. The smaller number, 8, has one digit, so Lamé's limit is five steps, and this pair reaches it. With quotients of 1, only one square comes off at each step until the last, and each leftover is nearly the shape of the rectangle before it.
A 10-minute graph-paper activity
Draw 60 by 24 and 21 by 13 on squared paper, one box per unit.
Before cutting, write your guess for the steps and the HCF of each.
Shade the largest squares batch by batch, one colour per batch, writing the division line beside it.
Stop when a batch fills its strip exactly: that square's side is the HCF. Check with prime factors.
Compare: 60 by 24 takes two steps (HCF 12), 21 by 13 takes six (HCF 1). Why is the Fibonacci pair slower?
For the textbook side, see our guide to HCF, LCM and irrationality proofs in Class 10 real numbers; for harder remainder questions, IOQM number theory questions on divisibility; and for the history, how Euclid's Elements began proof-based geometry.
When an idea clicks faster as a picture, the Fermi Simulation Lab has interactive simulations for ideas that are easier to see than to read. If an HCF problem has you stuck, the Fermi Problem Library has a step-by-step solver that explains the reasoning rather than printing an answer.
