Euclid’s Algorithm

Greatest common divisor

An interactive lesson with 7 steps, about 6 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• $\gcd(a, b) = \gcd(b, a \bmod b)$: repeat until the remainder is 0.
• $\text{lcm}(a, b) = \frac{ab}{\gcd(a, b)}$.
• Coprime numbers share no prime factor (their gcd is 1).

Steps

1. Biggest tile
2. Euclid’s algorithm
3. Run it
4. Euclid with scissors
5. Least common multiple
6. The biggest square tile
7. Coprime