Cutting Squares
Take two numbers as the sides of a rectangle and repeatedly cut off the biggest square. The side of the last square is the greatest common divisor of the two numbers. Compare it with the division lines.
Left: 48 × 18. 4 more cuts to a square.
How to play
The two numbers above set the sides of the rectangle. Press "Cut a square" and a square the size of the shorter side is cut off the longer side. When what is left is a square, you are done, and its side is the greatest common divisor. Each time a division line is finished, it appears next to the picture. "Hint" gives an idea, then the next square size, then the answer. "Auto-solve" lets the computer cut the rest and explain.
Learn more
The greatest common divisor of two numbers equals the greatest common divisor of the smaller number and the remainder when the larger is divided by the smaller. For 48 and 18, 48 = 2 x 18 + 12, so the problem becomes 18 and 12. Then 18 = 1 x 12 + 6 gives 12 and 6, and 12 = 2 x 6 + 0 leaves no remainder. The last divisor, 6, is the answer. On the rectangle, each step is "cut off the biggest square". It is a very old procedure, found in Euclid’s Elements, written in ancient Greece around the 3rd century BC. This page checks the result for every pair of numbers from 1 to 60 against a brute-force search for the largest common divisor.