Euclid's Algorithm — Find the Biggest Shared Measure with Paper Strips

A hands-on maths project: cut two paper strips of different lengths and repeatedly lay the shorter along the longer to find their greatest common measure -- Euclid's 2,300-year-old algorithm, done with your hands. A Python cell checks your answer, and a compendium shows why this simple recipe still runs inside computers.

初学者

30 minutes

说明

The greatest common measure

The greatest common divisor of two numbers is the largest number that divides both. Around 300 BC Euclid found a beautiful way to get it without factoring. You will do it as he did -- as lengths.

Cut two strips

Cut two strips of card, one 48 cm and one 18 cm (or any two lengths). The greatest common divisor is the longest ruler-length that measures BOTH strips a whole number of times.

此步骤所需材料：

Cardstock Assorted Pack (50 sheets)1 个

所需工具：

Sharp Scissors

Steel Ruler (30cm)

Lay the short along the long

Lay the 18 cm strip along the 48 cm strip as many whole times as it fits (twice, reaching 36), and mark the leftover (12 cm). Now repeat with the two smaller lengths: fit 12 into 18 once, leftover 6. Fit 6 into 12 exactly twice, no leftover. The last non-zero leftover, 6 cm, is the answer -- it measures both original strips exactly.

Check it

Loading Jupyter Notebook...

所需工具：

Desktop Computer

Calculator

Compendium: the oldest algorithm still running

What your strips reveal. (1) Each step replaces the longer length with the leftover, and it works because any length dividing both strips also divides the leftover. (2) It is astonishingly fast -- its very worst case is consecutive Fibonacci numbers, and even then it takes only a handful of steps for huge numbers. (3) The same idea reduces fractions to lowest terms (divide top and bottom by their GCD). (4) It is one of the oldest algorithms still in daily use, running billions of times a day inside the RSA encryption that protects online banking and messaging.