Labs / Mathematics
Euclid's Algorithm
Two numbers set the sides of a rectangle. The algorithm keeps carving off the biggest square it can, then repeats on whatever strip is left over. Tap the canvas or hit auto-run — the side of the very last square is the greatest common divisor of your two numbers.
rect 8 × 12squares 0GCD …
What to try
- Set a and b to two neighbouring Fibonacci numbers like 13 & 21. Why does the tiling take so many steps, and what is the GCD?
- Make one number an exact multiple of the other. How many different square sizes appear before it finishes?
- Switch to the Table view. Where does each square in the tiling show up as a quotient in the division rows?
- Can you find two numbers whose GCD is 1? What does a “GCD of 1” tiling look like compared with one that shares a big factor?
- Move a by one, then by two. Which small change causes the biggest jump in the number of steps — and can you predict it?